题目：

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<<left)-1;

			else {

				return countNodes(root.right)+countNodes(root.left)+1;

			}

		}

	 }

	 public static int  getRightHeight(TreeNode root) {

		 int height=0;

		 while(root!=null)

		 {

			 height++;

			 root=root.left;

		 }

		 return height;

	}

	 public static int  getLeftHeight(TreeNode root) {

		 int height=0;

		 while(root!=null)

		 {

			 height++;

			 root=root.right;

		 }

		 return height;

	}