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. It can have between 1 and 2h
nodes inclusive at the last level h.

一刷
题解：
首先算出leftmost的长度，和右孩子的leftmost长度。如果相差1，说明root的左子树为full。
如果相差2，说明root的右子树为full。然后recursion计算未算出来的那个子树。

/**
 * 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) {
       int h = height(root);
        if(h<0) return 0;
        int rightHeight = height(root.right);
        if(rightHeight == h-1)
            return (1<<h) + countNodes(root.right);//left part is full
        else return (1<<(h-1)) + countNodes(root.left);//right part is full
        
    }
    
    public int height(TreeNode root){
        return root==null? -1 : 1 + height(root.left);
    }
}

二刷同上，注意，根部的height为0

/**
 * 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) {
        int rootHeight = height(root);
        if(rootHeight < 0) return 0;
        int righgHeight = height(root.right);
        if(rootHeight == 1 + righgHeight){//left is full
            return (1<<rootHeight) + countNodes(root.right);
        }
        else{//right is full
            return (1<<rootHeight-1) + countNodes(root.left);
        }
    }
    
    public int height(TreeNode root){
        if(root == null) return -1;
        else return 1 + height(root.left);
    }
}