582. Kill Process

hashmap + DFS

T:O(n), n is the pid length

S:O(n)

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            map.putIfAbsent(ppid.get(i), new ArrayList<>());
            map.get(ppid.get(i)).add(pid.get(i));
        }
        List<Integer> result = new ArrayList<>();
        dfs(map, kill, result);
            
        return result;
    }
    private void dfs(Map<Integer, List<Integer>> map, int kill, List<Integer> result) {
        result.add(kill);
        System.out.println(kill);
        if (map.containsKey(kill)) { 
            // pid = [1,3,10,5], ppid = [3,0,5,3], 5 -> 10, but 10 is not parent, so not the map key
            for (int k : map.get(kill)) {
                dfs(map, k, result);
            }
        }
    }
}

/*
ppid[i] = 0
*/ja

hashmap + BFS

class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            map.putIfAbsent(ppid.get(i), new ArrayList<>());
            map.get(ppid.get(i)).add(pid.get(i));
        }
        List<Integer> result = new ArrayList<>();
        bfs(map, kill, result);
            
        return result;
    }
    private void bfs(Map<Integer, List<Integer>> map, int kill, List<Integer> result) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(kill);

        while (!queue.isEmpty()) {
            int curKill = queue.poll();
            result.add(curKill);

            if (map.containsKey(curKill)) {
                for (int k : map.get(curKill)) {
                    queue.offer(k);
                }
            }
        }
    }
}

/*
ppid[i] = 0
*/