582. Kill Process

T: O(n)

S:O(n)

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        
        Map<Integer, List<Integer>> tree = buildTree(pid, ppid);
        
        List<Integer> result = new ArrayList<>();
        result.add(kill); // add kill first

        dfs(tree, kill, result); // add kill's subtree
        return result;
    }
    
    private void dfs(Map<Integer, List<Integer>> tree, int kill, List<Integer> result) {
        if (tree.containsKey(kill)) {
            List<Integer> tmp = tree.get(kill);
            for (int s : tmp) {
                result.add(s);
                dfs(tree, s, result);
            }
        }
    }
    
    private Map<Integer, List<Integer>> buildTree(List<Integer> pid, List<Integer> ppid) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            int from = ppid.get(i);
            if (from != 0) {
                tree.putIfAbsent(from, new ArrayList<>());
                tree.get(from).add(pid.get(i));
            }
        }
        return tree;
    }
}

/*
When a process is killed, all of its children processes will also be killed.

give kill id
return a list of the IDs of the processes that will be killed.
find subtree

build graph

3 -> 1
3 -> 5 -> 10

1
2
3

1->2
2->3

*/ja