---
# System prepended metadata

title: 0582. Kill Process
tags: [Leetcode, BFS, DFS, Bloomberg, Medium]

---

# 0582. Kill Process
###### tags: `Leetcode` `Medium` `Bloomberg` `DFS` `BFS`
Link: https://leetcode.com/problems/kill-process/
## 思路 O(N) O(N)
先用map存每个parent，对应的所有孩子，然后进行DFS/BFS搜索
时间复杂度：需要将array遍历一遍
空间复杂度：因为用了map of size n
## Code
```java=
class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for(int i = 0;i < pid.size();i++){
            if(!tree.containsKey(ppid.get(i))){
                tree.put(ppid.get(i), new ArrayList<>());
            }
            tree.get(ppid.get(i)).add(pid.get(i));
        }
        
        Stack<Integer> stack = new Stack();
        stack.push(kill);
        res.add(kill);
        while(!stack.isEmpty()){
            int killpro = stack.pop();
            res.addAll(tree.getOrDefault(killpro, new ArrayList<>()));
            for(int nextKill:tree.getOrDefault(killpro, new ArrayList<>())){
                stack.push(nextKill);
            }
        }
        return res;
    }
}
```