Python, Straightforward with Explanation


  • 0

    Let's build the graph pictured in the question. Then, from the 'kill' process K, we want to kill the subtree at K. One way to do this is simply to traverse the subtree with a tree traversal algorithm, such as DFS.

    def killProcess(self, A, pA, kill):
        graph = collections.defaultdict(set)
        for child, parent in zip(A, pA):
            graph[parent].add(child)
        
        seen = set()
        def dfs(node):
            seen.add(node)
            for nei in graph[node]:
                if nei not in seen:
                    dfs(nei)
        
        dfs(kill)
        return list(seen)
    

Log in to reply
 

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