Binary Tree Vertical Order Traversal

• 从题目特点入手，知道结果数组里第一个和最后一个数组，是树的最左端和最右端。要获得这两个点，必须通过DFS不断的向左或者向右移动。如果以root为原点坐标来看，左边的层数为负数(min)，右边层数为正数。为了处理这个负数的问题，把坐标轴向右平移直到最左端层数为0。此时root的坐标恰好为(-min)
• 接着只需要对每一层的点进行判断，加入到对应位置的list中。于是很自然想到BFS。注意这里需要用两个Queue来保存node和他的位置

另外发现其实可以直接根据(col, List)使用HashMap进行保存，依旧是下一层往左的话，col-1，往右col+1，在保存的过程中，来找到边界值。最后再根据map和边界值来构建答案

//DFS+BFS
int min = 0;
    int max = 0;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        helper(root, 0);

        for (int i = min; i<=max; i++)
            res.add(new ArrayList<>());

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> index = new LinkedList<>();
        queue.add(root);
        index.add(-min);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int idx = index.poll();
            res.get(idx).add(cur.val);

            if (cur.left != null) {
                queue.add(cur.left);
                index.add(idx-1);
            }
            if (cur.right != null) {
                queue.add(cur.right);
                index.add(idx+1);
            }            
        }

        return res;
    }

    private void helper(TreeNode root, int level) {
        if (root == null) return;

        min = Math.min(min, level);
        max = Math.max(max, level);

        helper(root.left, level-1);
        helper(root.right, level+1); 
    }

//only BFS
public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }

    Map<Integer, ArrayList<Integer>> map = new HashMap<>();
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> cols = new LinkedList<>();

    q.add(root); 
    cols.add(0);

    int min = 0;
    int max = 0;

    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        int col = cols.poll();

        if (!map.containsKey(col)) {
            map.put(col, new ArrayList<Integer>());
        }
        map.get(col).add(node.val);

        if (node.left != null) {
            q.add(node.left); 
            cols.add(col - 1);
            min = Math.min(min, col - 1);
        }

        if (node.right != null) {
            q.add(node.right);
            cols.add(col + 1);
            max = Math.max(max, col + 1);
        }
    }

    for (int i = min; i <= max; i++) {
        res.add(map.get(i));
    }

    return res;
}