Fast pyhon iterative and recursive solutions (56ms)


  • 2
    C

    Most people use recursive solutions. I'm sharing my iterative solutions, which would be faster since it doesn't have to go through the entire tree (especially for extremely unbalanced trees). The ideas is based on Binary Tree Level Order Traversal. The best runtimes on OJ is 56ms.


    Solution 1-4 are based on similar ideas. Solution 4 is longer but easier to understand and should be the fastest.

    (I did some test, for big balanced trees, iterative Solution 3 and 4 are the fastest, faster than 1,2, and recursive solutions)




    Solution 1, iterative, shortest, 6 lines

    def minDepth(self, root):
        depth, level = 0, [root]
        while level and level[0]:
            depth += 1
            NotLast = (None,None) not in [(n.left, n.right) for n in level ]
            level = NotLast and [k for n in level for k in (n.left,n.right) if k]
        return depth
    

    (note: if NotLast=False, it would turn level into False and then leave the while loop)




    Solution 2, iterative, 8 lines

    def minDepth(self, root):
        depth, level = 0, [root]
        while level and level[0]:
            depth += 1
            for n in level:
                if not n.left and not n.right:
                    return depth
            level = [kid for n in level for kid in (n.left,n.right) if kid] 
        return depth 
    




    Solution 3, iterative, 10 lines

    def minDepth(self, root):
        depth, level = 0, [root]
        while level and level[0]:
            depth += 1
            temp = []
            for n in level:
                if not n.left and not n.right:
                    return depth
                temp.extend([kid for kid in (n.left, n.right) if kid])
            level = temp
        return depth
    




    Soltion 4, iterative, 14 lines. (An expansion of 1-3, easier to understand)

    def minDepth(self, root):
        depth, level = 0, [root]
        while level and level[0]:
            depth += 1
            temp = []
            for n in level:
                l, r = n.left, n.right
                if not l and not r:
                    return depth
                if l:
                    temp.append(l)
                if r:
                    temp.append(r)
            level = temp
        return depth   
    




    Solution 5, recursive, 5 lines

    def minDepth(self, root):
        if not root:
            return 0
        if not root.left or not root.right:
            return 1+max(self.minDepth(root.left),self.minDepth(root.right))
        return 1+min(self.minDepth(root.left),self.minDepth(root.right))

  • 0
    H

    Nice,i like your solutions.


  • 0
    T

    Thanks - the recursive solution was very helpful! I was having trouble with the leaf aspect of the problem.


Log in to reply
 

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