题解 | #完全二叉树结点数#

第一反应是没读懂题，因为会想到不是从上到下，从左到右遍历所有节点，save在list里，再用len()计算长度即可如下（但是时间复杂度貌似不符合）：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param head TreeNode类 
# @return int整型
#
class Solution:
    def nodeNum(self , head ):
        # write code here
        if head == None:
            return 0
        queue = [head]
        res = []
        while queue:
            node = queue.pop(0)
            res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return len(res)


或者更简单的方式是递归：
class Solution:
    def nodeNum(self , head ):
        # write code here
        # 特殊情况
        if not head:
            return 0
        return self.nodeNum(head.left) + self.nodeNum(head.right) + 1


但是其实也是遍历，其实不算优化算法，

优化算法有，但是一般可能不怎么想得到：  满二叉树是完全二叉树的一个特例， 如果是一个满2叉树 , 则套用公式 ， 2的树深次方-1
如果是满二叉树，再加上剩下的节点 class Solution:
    def nodeNum(self , head ):
        # write code here
        # 特殊情况
        if not head:
            return 0
        num_l = self.depth(head.left)
        num_r = self.depth(head.right)
        if num_l == num_r:
            return 2**num_l -1 + 1 + self.nodeNum(head.right)
        else:
            return 2**num_r -1 + 1 + self.nodeNum(head.left)
    def depth(self, root):
        cnt = 0
        while root != None:
            cnt += 1
            root = root.left
        return cnt