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:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
class Node implements Comparable<Node> {
int d;
int t;
int v;
public Node(int d, int v, int t) {
this.d = d;
this.v = v;
this.t = t;
}
@Override
public int compareTo(Node n) {
if (Integer.compare(d, n.d) == 0) {
return Integer.compare(t, n.t);
}
return Integer.compare(d, n.d);
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
Map<Integer, PriorityQueue<Node>> map = new HashMap();
int[] range = new int[]{0, 0};
int[] t = new int[]{0};
pre(root, map, 0, 0, range, t);
List<List<Integer>> result = new ArrayList();
for (int p = range[0]; p <= range[1]; p ++) {
if (map.containsKey(p)) {
PriorityQueue<Node> nodes = map.get(p);
List<Integer> curr = new ArrayList();
while (!nodes.isEmpty()) {
curr.add(nodes.poll().v);
}
result.add(curr);
}
}
return result;
}
private void pre(TreeNode root, Map<Integer, PriorityQueue<Node>> map, int d, int p, int[] range, int[] t) {
if (root == null) return;
t[0] ++;
map.putIfAbsent(p, new PriorityQueue());
map.get(p).add(new Node(d, root.val, t[0]));
range[0] = Math.min(range[0], p);
range[1] = Math.max(range[1], p);
if (root.left != null) {
pre(root.left, map, d + 1, p - 1, range, t);
}
if (root.right != null) {
pre(root.right, map, d + 1, p + 1, range, t);
}
}
}