给定一棵完全二叉树的根节点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;
}
}
