Python BFS


  • 0
    L

    Simple 2 step process. We assume that len(pid)==len(ppid) and then convert the two lists to graph using python dictionary. Then find a subtree rooted at kill node and return all its nodes in result by doing breadth first traversal.

    class Solution(object):
        def killProcess(self, pid, ppid, kill):
            """
            :type pid: List[int]
            :type ppid: List[int]
            :type kill: int
            :rtype: List[int]
            """
            # 1- Convert lists to graph.
            # 2- Find nodes of subtree rooted at kill node using BFS.
            # 3- return result
            res = []
            graph = collections.defaultdict(set)
            for i in range(0,len(pid)):
                graph[ppid[i]].add(pid[i])
            q = collections.deque([kill])
            while q:
                node = q.popleft()
                res.append(node)
                q += graph[node]
            return res
    

Log in to reply
 

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