边工作边刷题：70天一遍leetcode: day 67-2

Count Complete Tree Nodes

要点：递归的思路
复杂度：因为左右子树最差情况必然一个full一个complete，所以只有一边是继续递归的。另一边下一层就返回了。所以主定理：O(n)=O(n/2)+lgn => O(lgn)*O(lgn)
错误点：注意公式：2^h-1, h是binary tree实际高度，不是从0开始的深度

# 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
        """
        if not root: return 0
        depth = 0
        cur = root
        while cur.left:
            cur=cur.left
            depth+=1
        rh = 0
        cur = root
        while cur.right:
            cur=cur.right
            rh+=1
            
        #print depth,rh
        if rh==depth:
            return (1<<(depth+1))-1
            
        return self.countNodes(root.left)+self.countNodes(root.right)+1