314 Binary Tree Vertical Order Traversal

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

------------------
Solution #1, 树的level order，可以保证col内部node的顺序
额外的queue是为了记录当前node的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) {
        
        if (root == null) return new ArrayList<>();
        
        Map<Integer, List<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        int col = 0;
        q.add(root);
        cols.add(col);
        int minCol = 0;
        int maxCol = 0;
        
        while (!q.isEmpty()) {
            TreeNode top = q.poll();
            col = cols.poll();
            
            if (!map.containsKey(col)) {
                map.put(col,new ArrayList<Integer>());
            }
            map.get(col).add(top.val);
            
            if (top.left != null) {
                cols.add(col - 1);
                q.add(top.left);
                minCol = Math.min(minCol, col - 1);
            }
            
            if (top.right != null) {
                cols.add(col + 1);
                q.add(top.right);
                maxCol = Math.max(maxCol, col + 1);
            }
        }
        
        List<List<Integer>> rt = new ArrayList<>();
        for (int i = minCol; i <= maxCol; i++) {
            rt.add(map.get(i));
        }
        
        return rt;
    }
}