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 010         11         if self.depth(root, True) == self.depth(root, False):12             return 2** (self.depth(root, True)) - 113         else:14             return self.countNodes(root.left) + self.countNodes(root.right) +1 15         16     def depth(self, root, isLeft):17         ans = 018         while root:19             if isLeft == True:20                 root = root.left21             else:22                 root = root.right23             ans += 124         return ans