582. Kill Process

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        """tc O(N) sc O(N)
        main idea: hashmap to record parent -> child relation + BFS get kill process's children 
        """
        children = collections.defaultdict(list)
        # 1. build parent -> child  tree, find root 
        for parent, child in zip(ppid,pid):
            children[parent].append(child)
        res = [kill] # include self 
        if children[0] == kill:return pid # optimization 
        # BFS 
        q = collections.deque()
        for each in children[kill]:
            q.append(each)
        
        while q:
            cur = q.popleft()
            res.append(cur)
            for each in children[cur]:
                q.append(each)
        return res