The 'usual' implementation of BFS with visited array giving me TLE in python


  • 0
    A
    class Solution:
    # @param root, a tree node
    # @return an integer
    def minDepth(self, root):
        to_be_explored = collections.deque()
        visited = []
        count = 0
        if root == None:
            return 0
        to_be_explored.appendleft(root)
        visited.append(root)
        
        while to_be_explored:
            node = to_be_explored.pop()
            count += 1
            if node.right != None and  node.right not in visited: #<-----this check is O(n)
                to_be_explored.appendleft(node.right)
                visited.append(node.right)
            if node.left != None and node.left not in visited: : #<-----this check is O(n)
                to_be_explored.appendleft(node.left)
                visited.append(node.left) 
            
        return count

Log in to reply
 

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