LeetCode222. 完全二叉树的节点个数

LeetCode222. 完全二叉树的节点个数

 

背景知识:

  完全二叉树:除了最后一层,所有层的节点数达到最大,与此同时,最后一层的所有节点都在最左侧。(堆使用完全二叉树)

  满二叉树:所有层的节点数达到最大。一棵层数为 h 的满二叉树,其节点数为2^h - 1个。

 

思路1:层序遍历 或 递归 遍历整棵树。 但没用到 完全二叉树 的性质。。不可取

 

思路2:左神P178 ,        时间复杂度为O(h^2), h为完全二叉树的层数

  知识点1:层数为h的满二叉树的节点数为2^h - 1个

  知识点2:完全二叉树的高度可以直接通过不断地访问左子树就可以获取

 

具体步骤为:

  (1)如果不是空树,求完全二叉树的高度。求法是找到树的最左节点看能到哪一层,层数记为h

  (2)递归函数 bs(node, l ,h)的返回值表示以node为头的完全二叉树的节点数是多少。l表示node所在的层数,h表示整棵树的层数是始终不变的。初始时,node为头节点head, l 为 1

  找到node右子树的最左节点,如果能到达最后一层,见(2.1),如果不能,见(2.2)

    (2.1)第一种情况:说明node的整棵左子树是满二叉树,并且层数为h-l 。 node的整棵左子树再加上node本身,节点数为2^(h-l)-1+1. 此时再递归求出node右子树的节点数即可。 bs(node.right, l + 1, h) 。 因此,整体为2^(h-l)+bs(node.right, l + 1, h)

    (2.2)第二种情况:说明node的整棵右子树是满二叉树,层数为h-l-1. 同(2.1),整体为2^(h - l - 1) -1 + 1+bs(node.left, l + 1, h)

  (3)复杂度分析。 每一层只会选择一个节点node进行bs的递归过程,所以调用bs函数的次数为O(h)

           每次调用bs函数时,都会查看node右子树的左子节点,所以会遍历O(h)个节点,因此总的复杂度为O(h^2)

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        return bs(root, 1, mostLeftLevel(root, 1));
    }
    
    // 返回以node为根的完全二叉树的节点数是多少
    private int bs(TreeNode node, int curLevel, int level) {
        if (curLevel == level) {
            return 1;
        }
        // 对应情况2.1
        if (mostLeftLevel(node.right, curLevel + 1) == level) {
//            return (int)Math.pow(2,level - curLevel) + bs(node.right, curLevel + 1, level);
            return (1 << (level - curLevel)) + bs(node.right, curLevel + 1, level);
        }else { // 对应情况2.2
//            return (int)Math.pow(2,level - 1 - curLevel) + bs(node.left, curLevel + 1, level);
            return (1 << (level - 1 - curLevel)) + bs(node.left, curLevel + 1, level);
        }
    }
    
    // 求出以node为根的树的最左节点的层数
    private int mostLeftLevel(TreeNode node, int start) {
        while (node != null) {
            node = node.left;
            start ++;
        }
        return start - 1;
    }
}

 

上一篇:Python之爬虫系列之第一弹


下一篇:dd命令详解