Idea is pretty much the same as the way binary search works:
###Search if the right most child node exists in left sub-tree
If it exists, that means the left sub-tree is a perfect binary tree, so just add up those nodes by simple math and go to unfinished subtree, a.k.a, right sub-tree.
if not, that also means the right sub-tree will def have one level less than tree height, also apply simple math to this and keep digging into left-subtree until a perfect binary tree is found.
def hasFullNodes(root, depth): ptr = root for i in xrange(depth): if ptr is None: return False ptr = ptr.right return True class Solution(object): def countNodes(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return 0 if root.left is None: return 1 if root.right is None: return 2 ptr, depth = root, 0 while ptr is not None: ptr = ptr.left depth += 1 ptr = root count = 0 for i in xrange(depth-1, 0, -1): left, right = ptr.left, ptr.right if hasFullNodes(left, i): count += (2 ** i) - 1 ptr = right else: count += 2 ** (i-1) - 1 ptr = left count += 1 # ptr if i == 1 and ptr is not None: count += 1 # Corner case return count
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.