222. Count Complete Tree Nodes

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

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

算法1

(递归) $O((logN)^2)$

到了每一个node，一直向左看深度left，一直向右看深度right，如果left==right说明是full tree，就直接返回 (1 << left) - 1,如果不是的话就返回1 + count(node.left) + count(node.right).唯一的一点小小的优化就是，到下一层的时候，肯定有某一个hight是parent算过了，这种情况下就不需要再算一次，直接传到下一层递归。

Java 代码

    public int countNodes(TreeNode root) {
        return getNodeNum(root, -1, -1);
    }
    private int getNodeNum (TreeNode node, int leftHight, int rightHight) {
        if (leftHight == -1) {
            leftHight = 0;
            TreeNode curr = node;
            while(curr != null) {
                leftHight++;
                curr = curr.left;
            }
        }
        if (rightHight == -1) {
            rightHight = 0;
            TreeNode curr = node;
            while (curr != null) {
                rightHight++;
                curr = curr.right;
            }
        }
        if (leftHight == rightHight) {
            return (1 << leftHight) - 1;
        } else {
            return 1 + (getNodeNum(node.left, leftHight - 1, -1) + getNodeNum(node.right, -1, rightHight - 1));
        }
    }
}