314. Binary Tree Vertical Order Traversal

Given a binary tree,return the?vertical order?traversal 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 from?left to right.
Examples 1:
Input: [3,9,20,null,15,7]

   3
  / /   9  20
    /   /    15   7 

Output:

[
  [9],[3,15],[20],[7]
]
Examples 2:
Input: [3,8,4,1,7]

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

Output:

[
  [4],[9],1],[8],[7]
]
Examples 3:
Input: [3,7,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],[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 {
    class Pair{
        TreeNode node;
        Integer pos;
        
        public Pair(TreeNode node,Integer pos){
            this.node = node;
            this.pos = pos;
        }
    }
    public List<List<Integer>> verticalOrder(TreeNode root) {
        HashMap<Integer,List<Integer>> map = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        
        Queue<Pair> queue = new LinkedList<>();
        Integer max = 0;
        Integer min = 0;
        
        queue.offer(new Pair(root,0));
        while(!queue.isEmpty()){
            Pair cur = queue.poll();
            Integer curPos = cur.pos;
            TreeNode curNode = cur.node;
            
            if(!map.containsKey(curPos)){
                map.put(curPos,new ArrayList<>());
            }
            map.get(curPos).add(curNode.val);
            
            if(curNode.left != null){
                min = Math.min(min,curPos - 1);
                queue.offer(new Pair(curNode.left,curPos - 1));
            }
            
            if(curNode.right != null){
                max = Math.max(max,curPos + 1);
                queue.offer(new Pair(curNode.right,curPos + 1));
            }
        }
        for(int i = min; i <= max; i++){
            
            result.add(map.get(i));
        }
        return result;
    }
}





class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
      HashMap<Integer,List<Integer>> map = new HashMap<>();
      List<List<Integer>> result = new ArrayList<>();
      Queue<TreeNode> queue = new LinkedList<>();
      Queue<Integer> cols = new LinkedList<>();
      
      if(root == null){
        return result;
      }
      
      int max = 0;
      int min = 0;
      
      queue.offer(root);
      cols.offer(0);
      while(!queue.isEmpty()){
        TreeNode cur = queue.poll();
        int col = cols.poll();
        if(!map.containsKey(col)){
          map.put(col,new ArrayList<Integer>());
        }
        map.get(col).add(cur.val);
        
        if(cur.left != null){
          queue.offer(cur.left);
          cols.offer(col - 1);
          min = Math.min(min,col - 1);
        }
        
        if(cur.right != null){
          queue.offer(cur.right);
          cols.offer(col + 1);
          max = Math.max(max,col + 1);
        }
      }
      
      for(int i = min; i <= max; i++){
        List<Integer> current_col = map.get(i);
        result.add(current_col);
      }
      return result;
    }
}