題目
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:
Given binary tree [3,9,20,null,null,15,7],
3
/\
/ \
9 20
/\
/ \
15 7
return its vertical order traversal as:
[
[9],
[3,15],
[20],
[7]
]
答案
Similar to level order traversal, but need to use an extra queue to keep track of column number, also a map to keep track of tree nodes in each column
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
if(root == null) return new ArrayList<List<Integer>>(); ;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Queue<Integer> columnq = new LinkedList<Integer>();
Map<Integer, List<Integer>> map = new HashMap<>();
List<List<Integer>> lists = new ArrayList<List<Integer>>();
q.offer(root);
columnq.offer(0);
while(q.size() != 0) {
int curr_size = q.size();
for(int i = 0; i < curr_size; i++) {
TreeNode t = q.poll();
Integer column = columnq.poll();
List<Integer> list = map.get(column);
if(list == null) {
list = new ArrayList<>();
map.put(column, list);
}
list.add(t.val);
if(t.left != null) {
q.offer(t.left);
columnq.offer(column - 1);
}
if(t.right != null) {
q.offer(t.right);
columnq.offer(column + 1);
}
}
}
int min = Collections.min(map.keySet());
int max = Collections.max(map.keySet());
for(int i = min; i <= max; i++) {
lists.add(map.get(i));
}
return lists;
}
}
