314. Binary Tree Vertical Order Traversal

Medium
第一眼看上去很难，其实看清楚column之间的关系就还好。col之间的关系就是左孩子比根少1， 右孩子比根多1. 基本方法是BFS + HashMap

我们用一个map来保存每个col上所拥有的节点，key为col, value为a list of nodes' value. 保留一个max, min col 并随时更新以便最后遍历返回结果. 注意我们做BFS的时候需要两个queue, 一个用来装treeNode对树进行bfs; 一个装col number用来配合树做col的BFS. 这样我们在BFS中每poll出来一个treenode和一个col, 首先check map里面有没有这个col. 再在相应的key的value while is a list里面加上这个curt node的val. 接下来检查curt node的左右子树. 如果不为null, 一是要加到treenode queue里面进行宽搜，二是要把col-1（col+1)加到col queue里面，并且要记得更新min col(max col).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int max = 0;
        int min = 0;
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        Queue<Integer> colQueue = new LinkedList<>();
        treeNodeQueue.offer(root);
        colQueue.offer(0);
        while (!treeNodeQueue.isEmpty()){
            TreeNode curt = treeNodeQueue.poll();
            int col = colQueue.poll();
            if (!map.containsKey(col)){
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(curt.val);
            if (curt.left != null){
                treeNodeQueue.offer(curt.left);
                colQueue.offer(col - 1);
                min = Math.min(min, col - 1);
            }
            if (curt.right != null){
                treeNodeQueue.offer(curt.right);
                colQueue.offer(col + 1);
                max = Math.max(max, col + 1);
            }
        }
        for (int i = min; i <= max; i++){
            res.add(map.get(i));
        }
        return res;
    }
}