My simple iterative BFS solution in python

  • 2
    class Solution:
        # @param root, a tree node
        # @return an integer
        def minDepth(self, root):
            if not root:
                return 0
            explored = [(root, 1)]
            while explored:
                (node, depth) = explored.pop(0)
                if node.left is node.right is None:
                    return depth
                if node.left:
                    explored.append((node.left, depth+1))
                if node.right:
                    explored.append((node.right, depth+1))

    I store explored nodes with their depth. Notice that I add new nodes to the end (.append()) while I take them from the head (.pop(0)) -- in this way I am sure to always find the shortest depth nodes first.

Log in to reply

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