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

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

二月 23, 2020

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

给出一个完全二叉树，求出该树的节点个数。

说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:
输入:
    1
 /       \
2       3
/ \     /
4 5  6

输出: 6

利用完全二叉树的特性

用左子树的深度是否等于右子树的深度来划分。

  • 当左子树等于右子树的深度的时候，左子树和节点个数可以通过深度求出来。count=2^depth^-1.再加上当前的根节点，所以现在知道的节点个数为 2^depth^。即算出来1,2,4,5对应的节点个数，为4。下一步需要对右子树查找。
  • 如果左子树的深度不等于右子树的深度，说明右子树的最后一层不是满的。算出右子树的节点个数加上根节点，也是2^depth^。再对左子树查找。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int countNodes(TreeNode root) {
            if(root == null){
               return 0;
            } 
            int left = depth(root.left);
            int right = depth(root.right);
            if(left == right){
                return countNodes(root.right) + (1<<left);
            }else{
                return countNodes(root.left) + (1<<right);
            }
        }
        private int depth(TreeNode root){
            int depth = 0;
            while(root != null){
                depth++;
                root = root.left;
            }
            return depth;
        }
    leetcode 32/100