Python BFS O(n) time with Queue and Dict


  • 0
    N
    
    def killProcess(self, pid, ppid, kill):
    
            d = dict()
            for i,v in enumerate(ppid):
                if v in d:
                    d[v].append(pid[i])
                else:
                    d[v]=[pid[i]]
            queue = [kill]
            ans =[]
            while len(queue) != 0:
                cur = queue.pop(0)
                if cur in d:
                    queue += d[cur]
                ans.append(cur)
            return ans
    

  • 0
    N

    Small change to DFS:

    class Solution(object):
        def killProcess(self, pid, ppid, kill):
            """
            :type pid: List[int]
            :type ppid: List[int]
            :type kill: int
            :rtype: List[int]
            """
            d = dict()
            for i,v in enumerate(ppid):
                if v in d:
                    d[v].append(pid[i])
                else:
                    d[v]=[pid[i]]
            stack = [kill]
            ans =[]
            while len(stack) != 0:
                cur = stack.pop()
                if cur in d:
                    stack += d[cur]
                ans.append(cur)
            return ans
    

Log in to reply
 

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