L314. Binary Tree Vertical Order Traversal

Problem:

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,null,15,7]

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

Output:

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

Solution:

• 用两个queue，一个存level上的node，一个存vertical上的column的信息。用一个hashmap存column的信息和arraylist，arraylist存的是node的value

public List<List<Integer>> vertical(TreeNode root){
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) return res;
    
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    
    Queue<TreeNode> levelQue = new LinkedList<>();
    Queue<Integer> colQue = new LinkedList<>();
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    levelQue.offer(root);
    colQue.offer(0);
        
    while(!levelQue.isEmpty()){
        TreeNode pollNode = levelQue.poll();
        int col = colQue.poll();
            
        min = Math.min(col, min);
        max = Math.max(col, max);
        //更新hashmap里面存的值
        if(map.containsKey(col)){
            map.get(col).add(pollNode.val);
        }else{
            ArrayList<Integer> list = new ArrayList<>();
            list.add(pollNode.val);
            map.put(col, list);
        }
        //更新queue里面存的值
        if(pollNode.left != null){
            levelQue.offer(pollNode.left);
            colQue.offer(col - 1);
        }
            
        if(pollNode.right != null){
            levelQue.offer(pollNode.right);
            colQue.offer(col + 1);
        }
    }
    for(int i = min; i <= max; i++){
        res.add(map.get(i));
    }
        
    return res;

}