582. Kill Process

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:

Input: 
pid =  [1, 3, 10, 5, 12, 13]
ppid = [3, 0, 5, 3, 5, 12]
kill = 5
Output: [5,10]
Explanation: 
           3
         /   \
        1     5
             /   \
            10   12
                  \
                    13
Kill  5will also kill 10, 12, 13.
Note:
The given kill id is guaranteed to be one of the given PIDs.
n >= 1.

思路

1. 由于pid和paid都一一对应关系，所以可以将其转换成HashMap来表示其关系，例题中的关系图表示如下：

key: value  (PPID, PID)
0: 3
3: 1, 5
5: 10,12
12: 13

如果要kill 5，那么除了5本身外，5对应的10，12要kill，12下面的13要kill。很自然想到BFS。

2. 用BFS方法，不断找指定要kill的元素下面得pid。找到后放入queue，再找其下面的pid，一直找到queue 为空，则找到了所有需要kill的pid

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        if (pid == null || ppid == null || pid.size() != ppid.size()) return null;
        
        //1. Hashmap to store the ppid and pid relationship
        HashMap<Integer, List<Integer>> mapping = new HashMap<>();
        
        for(int i = 0; i < ppid.size(); i++) {
            mapping.put(ppid.get(i), new ArrayList<Integer>());
        }
        
        for(int i = 0; i < ppid.size(); i++) {
            mapping.get(ppid.get(i)).add(pid.get(i));
        }
        
        //2. 用BFS在hashmap中找，已知的要kill的process下面都有哪些pid，然后把这些pid再次加入到queue中再找其下面的pid，直到全部找完     
        List<Integer> result = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(kill);
        
        while (!queue.isEmpty()) {
            int curNode = queue.poll();
            result.add(curNode);
            
            if (mapping.get(curNode) != null) {
                List<Integer> temp = mapping.get(curNode);
                for (int i = 0; i < temp.size(); i++) {
                    queue.add(temp.get(i));
                }
            }
        }
        
        return result;
    }
}