[LeetCode] 314. 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
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
//store <column, node list>
Map<Integer, List<Integer>> map = new HashMap<>();
//store min col, max col
int min = 0, max = 0;
//store TreeNode
Queue<TreeNode> queue = new LinkedList<>();
//store column number
Queue<Integer> colqueue = new LinkedList<>();
//queue's elements are mapped to colqueue's elements
//e.g. root's column number is 0
queue.offer(root);
colqueue.offer(0);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int col = colqueue.poll();
if (!map.containsKey(col)) {
map.put(col, new ArrayList<Integer>());
}
map.get(col).add(node.val);
if (node.left != null) {
queue.offer(node.left);
colqueue.offer(col-1);
min = Math.min(min, col-1);
}
if (node.right != null) {
queue.offer(node.right);
colqueue.offer(col+1);
max = Math.max(max, col+1);
}
}
for (int i = min; i <= max; i++) {
res.add(map.get(i));
}
return res;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论