Python BFS

  • 0

    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)):
            q = collections.deque([kill])
            while q:
                node = q.popleft()
                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.