题目：

?

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.

解题：

如果用常规的解法一个个遍历，就是O(n)时间复杂度 ，会不通过，这边就不写O(n)的代码了。因为是完全二叉树，满二叉树有一个性质是节点数等于2^h-1,h为高度，所以可以这样判断节点的左右高度是不是一样，如果是一样说明是满二叉树，就可以用刚才的公式，如果左右不相等就递归计算左右节点。

代码：

?

public static int countNodes(TreeNode root) {
		 if(root==null)
			 return 0;
		 else {
			int left=getLeftHeight(root);
			int right=getRightHeight(root);
			if(left==right)
				return (1<
  
   
?
   
?