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

 3
/\

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

Output:

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

Solution

将node按照列放入map
使用Treemap记录key的顺序

注意点:
1. DFS不可行,无法保证同一列的node 至定向下输出

Complexity

O(N) O(N)

Code

/**
 * 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>> res = new ArrayList<>();
        if( root == null ) return res;
        
        
        
        Map<Integer, List<Integer>> map = new TreeMap<>();
        Deque<TreeNode> dq = new ArrayDeque<>();
        Deque<Integer> cols = new ArrayDeque<>();
        
        dq.offer(root);
        cols.offer(0);
        
        while(!dq.isEmpty()){
            TreeNode node = dq.poll();
            Integer col = cols.poll();
            
            if(!map.containsKey(col)){
                map.put(col, new ArrayList<Integer>());
            }
            
            List<Integer> tmp = map.get(col);
            tmp.add(node.val);
            
            if(node.left != null){
                dq.offer(node.left);
                cols.offer(col - 1);
            }
            if(node.right != null){
                dq.offer(node.right);
                cols.offer(col + 1);
            }
        }
        
        return new ArrayList<>(map.values());
        
    }
}