给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。
给定树的根结点root，请返回树的大小。

思路

先计算出左右子树的高度leftSubHgt和rightSubHgt.
如果leftSubHgt和rightSubHgt相等,说明左子树一定是一颗满二叉树,满二叉树在求得其高度的情况下可以算出总结点的数量, 此外可以对右子树进行递归调用,求得其节点数量.再加上根节点,就可以算出结果.
如果leftSubHgt和rightSubHgt不相等,说明右子树一定是一颗满二叉树.同理对左子树进行递归处理,最后也可得结果.

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class CountNodes {
    public int count(TreeNode root) {
        if(root==null)return 0;
        int leftSubHgt= TreeHieght(root.left);
        int rightSubHgt= TreeHieght(root.right);
        
        if(leftSubHgt==rightSubHgt){
            return 1+allNodes(leftSubHgt)+count(root.right);
        }
        else{
            return 1+allNodes(rightSubHgt)+count(root.left);
        }
    }
    
    //计算完全二叉树的高度,根节点为1
    private int TreeHieght(TreeNode node){       
        int height=0;
        while(node!=null){
            node=node.left;
            height++;
        }
        return height;
    }
    
    //计算高度为h的完全二叉树的节点数量
    private int allNodes(int h){
        return (int)Math.pow(2,h)-1;
    }
}