题目：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.
思路：如果知道一个子树是完全二叉树，并且其深度为h，那么这棵子树所包含的节点个数便为2^h-1。否则便需递归求其左右子树的节点个数。
代码：
def getHightRight(self, root):
if root == None:
return 0
high = 0
while root != None:
high += 1
root = root.right
return high
def getHightLeft(self, root):
if root == None:
return 0
high = 0
while root != None:
high += 1
root = root.left
return high
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
l_high = self.getHightLeft(root.left)
r_high = self.getHightRight(root.right)
if l_high == r_high:
return 2**(l_high+1)-1
else:
return self.countNodes(root.left)+self.countNodes(root.right)+1
