complete binary tree (CBT) 的定义和 Full binary tree (FBT)类似。如果上图中这个深度为3的binary tree有15个node （2**depth - 1）, 那么这个深度为3的binary tree就被填满了，是FBT。
上图中是一个CBT，因为他的所有12个node和FBT的前12个node位置相同。
思路： 沿着左臂一直往下找，和沿着右臂往下找的深度相同，那么这个树肯定是FBT，那么Node的个数就是2**depth - 1。否则就递归调用countNode。
1 class Solution(object): 2 def countNodes(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: int 6 """ 7 8 if not root: 9 return 0 10 11 if self.depth(root, True) == self.depth(root, False): 12 return 2** (self.depth(root, True)) - 1 13 else: 14 return self.countNodes(root.left) + self.countNodes(root.right) +1 15 16 def depth(self, root, isLeft): 17 ans = 0 18 while root: 19 if isLeft == True: 20 root = root.left 21 else: 22 root = root.right 23 ans += 1 24 return ans
Leetcode 222. Count Complete Tree Nodes
原文：http://www.cnblogs.com/lettuan/p/6367184.html