Leetcode 222. Count Complete Tre

Given a complete binary tree, count the number of nodes.Definition of a complete binary tree from [Wikipedia].
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
nodes inclusive at the last level h.

思路：
自己只想到了用宽度优先搜索来计算总节点数，时间复杂度是O(n)。
查看discuss中解答，发现了很多O(logn)解法，其核心想法是，通过计算根节点左右子树的高度，判断树最后一行中，最后一个叶子节点是在左子树还是右子树上。通过这样一次判断，可以立即减少一倍的搜索范围，之后只需要递归查找最后叶子节点所在的子树即可。

int height(TreeNode root) {
    return root == null ? -1 : 1 + height(root.left);
}
public int countNodes(TreeNode root) {
    int h = height(root);
    return h < 0 ? 0 :
            height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                    : (1 << h-1) + countNodes(root.left);
}