題目：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.

思路：如果知道一個(gè)子樹是完全二叉樹，并且其深度為h，那么這棵子樹所包含的節(jié)點(diǎn)個(gè)數(shù)便為2^h-1。否則便需遞歸求其左右子樹的節(jié)點(diǎn)個(gè)數(shù)。

代碼：

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