582. Kill Process

 一刷 07/2022

Version #1 Build Graph + BFS

写了一个bug就是有可能一个process是没有children的，那么它就不存在于我们build的children map里面，所以无脑取的话就会报null pointer exception

这里告诉我们每次写map.get的时候都要好好想想会不会为null

Time O(N)

Space O(N)

Runtime: 47 ms, faster than 40.16% of Java online submissions for Kill Process.

Memory Usage: 76.6 MB, less than 33.42% of Java online submissions for Kill Process.

class Solution {

    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {

        Map<Integer, List<Integer>> children = new HashMap<>();

        for (int i = 0; i < pid.size(); i++) {

            int id = pid.get(i);

            int parent = ppid.get(i);

            children.putIfAbsent(parent, new ArrayList<>());

            children.get(parent).add(id);

        }

        Queue<Integer> que = new ArrayDeque<>();

        que.offer(kill);

        List<Integer> result = new ArrayList<>();

        while (!que.isEmpty()) {

            int id = que.poll();

            result.add(id);

            if (!children.containsKey(id)) {

                continue;

            }

            for (int next : children.get(id)) {

                que.offer(next);

            }

        }

        return result;

    }

}