weekly contest32第二题。杀死父进程就同时杀死子进程，指定一个进程求会杀死哪些进程。

Example 1:
Input: 
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation: 
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

我的想法(超时了，O(n²))，类似DFS：用QUEUE保存要杀死的进程，拿出一个就杀死一个，同时在ppid里找有没有这个要被杀死的进程（有的话说明pid里有它的子进程），加入到queue里面去，直到queue为空。虽然超时了，但是思路似乎是对的。

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> killList = new LinkedList<>();
        killList.offer(kill);
        while (!killList.isEmpty()) {
            int temp = killList.poll();
            res.add(temp);
            for (int i = 0; i < pid.size(); i++) {
                if (ppid.get(i) == temp) {
                    killList.offer(pid.get(i));
                }
            }
        }
        return res;
    }

Editorial Solutions里有四种解法：
Approach #1 Depth First Search [Time Limit Exceeded]
Approach #2 Tree Simulation [Accepted]
Approach #3 HashMap + Depth First Search [Accepted]
Approach #4 HashMap + Breadth First Search [Accepted]:

Approach #1 DFS

跟我上面的想法类似，每次都用for循环在ppid里找可以作为parent的child process。

    public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
        List < Integer > l = new ArrayList < > ();
        if (kill == 0)
            return l;
        l.add(kill);
        for (int i = 0; i < ppid.size(); i++)
            if (ppid.get(i) == kill)
                l.addAll(killProcess(pid, ppid, pid.get(i)));
        return l;
    }

Approach #4 HashMap + Breadth First Search [Accepted]:

这解法思路看起来怎么还是跟我那个差不多呢，我就在想他的复杂度优化在哪里。他的思路是每次把除了0以外的每个node的direct child保存成hashmap，key是node，value是这个node对应的direct child的list。然后同样用一个queue来模拟bfs。
感觉上它这个方法虽然用了while+for，但确实似乎是O(n)，它快的地方是不需要每次都重新在一个很大的ppid集合里面找新的parent了，而只需要containsKey来找新的parent。

public class Solution {

    public List < Integer > killProcess(List < Integer > pid, List < Integer > ppid, int kill) {
        HashMap < Integer, List < Integer >> map = new HashMap < > ();
        for (int i = 0; i < ppid.size(); i++) {
            if (ppid.get(i) > 0) {
                List < Integer > l = map.getOrDefault(ppid.get(i), new ArrayList < Integer > ());
                l.add(pid.get(i));
                map.put(ppid.get(i), l);
            }
        }
        Queue < Integer > queue = new LinkedList < > ();
        List < Integer > l = new ArrayList < > ();
        queue.add(kill);
        while (!queue.isEmpty()) {
            int r = queue.remove();
            l.add(r);
            if (map.containsKey(r))
                for (int id: map.get(r))
                    queue.add(id);
        }
        return l;
    }
}