Given a binary tree, return thevertical ordertraversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be fromleft to right.

Examples 1:

Input:
[3,9,20,null,null,15,7]


   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 


Output:


[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: 
[3,9,8,4,0,1,7]


     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 


Output:


[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Examples 3:

Input:
[3,9,8,4,0,1,7,null,null,null,2,5]
 (0's right child is 2 and 1's left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2


Output:


[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

/**
 * 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>> ans = new ArrayList<>();
        if (root == null) return ans;

        Map<Integer, List<Integer>> hash = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> indexQ = new LinkedList<>();
        q.offer(root);
        indexQ.offer(0);

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        while (!q.isEmpty()){
            TreeNode cur = q.poll();
            int index = indexQ.poll();

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

            if (!hash.containsKey(index)){
                List<Integer> temp = new LinkedList<>();
                temp.add(cur.val);
                hash.put(index, temp);
            }
            else{
                hash.get(index).add(cur.val);
            }

            if (cur.left != null){
                q.offer(cur.left);
                indexQ.offer(index - 1);
            }

            if (cur.right != null){
                q.offer(cur.right);
                indexQ.offer(index + 1);
            }
        }

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

        return ans;
    }
}