My Python solution with O(h^2) time complexity


  • 0
    G

    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

  • 0
    S

    Why it is O(h) rather than O(h^2)?


  • 0
    G

    true. Forgot to add up hasFullNodes complexity. Thanks for the heads up!


  • 0
    S

    Not a problem. I am thinking about if an O(h) algorithm would possibly exist. Do you think if you solution can be optimized to O(h)?


  • 0
    G

    Beats me, can't think of O(h) solutioin...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.