1，这道题如果纯用递归数点而不利用其为一个complete binary tree的话会超时。
2.为了利用这个条件，比较左右两子数的高度：1， 如果相等则左子树为完全二叉树 2， 如果不等， 则右子树为完全二叉树。
3，完全二叉树的node个数为pow(2,depth)-1， 因此可以不用递归数点节约时间。
4，因为是complete binary tree，子树的深度只用一直找寻左儿子即可得到深度
总体复杂度O(lgn * lgn)
class Solution: # @param {TreeNode} root # @return {integer} def countNodes(self, root): if not root: return 0 leftDepth = self.getDepth(root.left) rightDepth = self.getDepth(root.right) if leftDepth == rightDepth: return pow(2, leftDepth) + self.countNodes(root.right) else: return pow(2, rightDepth) + self.countNodes(root.left) def getDepth(self, root): if not root: return 0 return 1 + self.getDepth(root.left)
原文：http://www.cnblogs.com/dapanshe/p/4625853.html