给定根节点，求这个完全二叉树的节点个数

[leetcode222]https://leetcode.com/problems/count-complete-tree-nodes/

思路

完全二叉树只有最后一层的节点会不满，上边层都是满的，而且最下面一层又是从左往右分布的。

算法步骤&原理

首先看求解树高度h，然后看根节点右子树的高度hr，如果h-hr==1，证明原数的左子树是满的，那么左子树的节点就可以得到，而右子树同理递归。否则，证明左子树是满的，同理搞定。
复杂度O(log(n)^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) {
        int h=height(root);
        int nums=0;
        while(root!=null){
            if(h-1==height(root.right)){
                nums+=1<<h;
                root=root.right;
            }
            else{
                nums+=1<<h-1;
                root=root.left;
            }
            h--;
        }
        return nums;
    }
    public int height(TreeNode root){
        return root==null?-1:height(root.left)+1;
    }
}