222. Count Complete Tree Nodes - jiejackyzhang/leetcode-note GitHub Wiki

Given a complete binary tree, count the number of nodes.

这里我们需要充分利用complete binary tree的特性。

如果用array来表示完全二叉树，index从1开始，则节点a[i]的左右孩子分别在a[2i]和a[2i+1]处。 注意到last node的index即为所有nodes的个数。 因此这里我们可以维护一个表示index的变量count，初值为1。

如果左子树的高度比右子树大，则说明last node在左子树中，count = count*2，指向root.left； 如果左右子树的高度相同，则说明last node在右子树中，count = count*2+1，指向root.right。

当root.left == null时，已到last level，并且此时root即为last node，因此此刻的count即为nodes的总数。

从root到leaf一共有h=logn次iteration，每个iteration中调用getHeight()，时间复杂度为O(h)，因此总的时间复杂度为O(h^2)。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int count = 1;
        while(root.left != null) {
            if(getHeight(root.left) > getHeight(root.right)) {
                root = root.left;
                count = count * 2;
            } else {
                root = root.right;
                count = count * 2 + 1;
            }
        }
        return count;
    }
    
    private int getHeight(TreeNode root) {
        int height = -1;
        while(root != null) {
            root = root.left;
            height++;
        }
        return height;
    }
}