222. Count Complete Tree Nodes

可以用遍历法求，但是不能判断是不是complete，且为O(n)的时间复杂度

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

是一个很迷的递归，

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = getDepth(root.left);
    int rightDepth = getDepth(root.right);
    if (leftDepth == rightDepth) {
        return (int) (countNodes(root.right) + Math.pow(2, leftDepth));
    }
    else {
        return (int) (countNodes(root.left) + Math.pow(2, rightDepth));
    }
}

public int getDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + getDepth(root.left);
}

补一下二叉树的性质：

1.第i层有2^(i-1)个节点。如第二层有2^(2-1)=2个节点

2.深度为k的二叉树最多有2^k-1个节点。如三层的树最多有2^3-1=7个节点

3.对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为n2, 则n0＝n2＋1。

4.具有 n (n>=0) 个结点的完全二叉树的深度为⌊log(n)⌋+1。如4个节点的树有⌊log(4)⌋+1=3层。