222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

<u style="box-sizing: border-box;">Definition of a complete binary tree from Wikipedia:</u>
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 2^h nodes inclusive at the last level h.

222：完全二叉树求高度，只需要往左边走

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def getHeight(r):
            if not r: return 0
            return 1+getHeight(r.left)
        
        if not root: return 0
        l, r = getHeight(root.left), getHeight(root.right)
        if l==r:
            return 2**l + self.countNodes(root.right)
        else:
            return 2**r + self.countNodes(root.left)