582.Kill Process

Solution 1: Queue + HashMap O(N)

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> parentChildMap = new HashMap<>();
        for(int i = 0; i < pid.size(); i++){
            int parent = ppid.get(i);
            int child = pid.get(i);
            if(parentChildMap.containsKey(parent)){
                List<Integer> childList = parentChildMap.get(parent);
                childList.add(child);
            }
            else{
                List<Integer> childList = new ArrayList<>();
                childList.add(child);
                parentChildMap.put(parent, childList);
            }
        }

        Queue<Integer> killQueue = new LinkedList<Integer>();
        List<Integer> killedProcess = new ArrayList<>();
        killQueue.add(kill);
        while(!killQueue.isEmpty()){
            int killedPid = killQueue.poll();
            killedProcess.add(killedPid);
            if(parentChildMap.containsKey(killedPid)){
                List<Integer> childProcessList = parentChildMap.get(killedPid);
                for(Integer childPid : childProcessList){
                    killQueue.add(childPid);
                }
            }
        }
        return killedProcess;
    }
}