582. Kill Process

很简单的BFS应用，最开始直接在BFS过程中找数TLE了，就先用hashmap预处理一下。

public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> result = new ArrayList<>();
        if (pid == null || ppid == null || pid.size() == 0 || ppid.size() == 0) return result;

        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < pid.size(); ++i) {
            int curtPID = pid.get(i);
            int curtPPID = ppid.get(i);
            if (map.containsKey(curtPPID)) {
                List<Integer> list = map.get(curtPPID);
                list.add(curtPID);
                map.put(curtPPID, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(curtPID);
                map.put(curtPPID, list);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(kill);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                result.add(node);
                List<Integer> next = map.get(node);
                if (next == null || next.size() == 0) continue;
                for (int j : next) queue.offer(j);
            }
        }
        return result;
    }
}

314. Binary Tree Vertical Order Traversal

这里列数的定义我们可以理解为，root为0，向左就是-1，向右就是+1。然后再用BFS来确定顺序。

用两个变量确定最小列数和最大列数，这样可以最后遍历map装进list。

public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        int colMin = 0;
        int colMax = 0;

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

        Queue<Integer> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();

        q1.offer(0);
        q2.offer(root);

        while (!q1.isEmpty()) {
            int c = q1.poll();
            TreeNode node = q2.poll();

            if (map.containsKey(c)) {
                List<Integer> list = map.get(c);
                list.add(node.val);
                map.put(c, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(node.val);
                map.put(c, list);
            }

            colMin = Math.min(colMin, c);
            colMax = Math.max(colMax, c);

            if (node.left != null) {
                q1.offer(c - 1);
                q2.offer(node.left);
            }
            if (node.right != null) {
                q1.offer(c + 1);
                q2.offer(node.right);
            }
        }

        for (int i = colMin; i <= colMax; ++i) {
            result.add(map.get(i));
        }   
        return result;
    }
}