-
Notifications
You must be signed in to change notification settings - Fork 1
/
VerticalOrderTraversalBinaryTree.java
76 lines (64 loc) · 2.15 KB
/
VerticalOrderTraversalBinaryTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
/**
* 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 {
TreeMap<Integer , List<int[]>> colMap; // Treemap to sort by col and int[] {val , pos} of row to help sort later
public List<List<Integer>> verticalTraversal(TreeNode root) {
colMap = new TreeMap<>();
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(root,0,0));
while(queue.size() > 0){
Queue<Node> level = new LinkedList<>();
while(queue.size() > 0){
Node node = queue.poll();
int r = node.row;
int c = node.col;
TreeNode n = node.node;
List<int[]> list = colMap.getOrDefault(c,new ArrayList<>());
list.add(new int[]{n.val,r});
colMap.put(c,list);
if(n.left != null){
queue.offer(new Node(n.left,r+1,c-1));
}
if(n.right != null){
queue.offer(new Node(n.right,r+1,c+1));
}
}
queue = level;
}
List<List<Integer>> result = new ArrayList<>();
for(int i : colMap.keySet()){
List<int[]> list = colMap.get(i);
Collections.sort(list,(a,b)->((a[1] == b[1])? a[0]-b[0] : a[1]-b[1])); // if same row then sort by val
List<Integer> r = new ArrayList<>();
for(int[] arr : list){
r.add(arr[0]);
}
result.add(r);
}
return result;
}
}
class Node{
TreeNode node;
int row;
int col;
public Node(TreeNode node, int row , int col){
this.node = node;
this.col = col;
this.row = row;
}
}