PROBLEM DESCRIPTION
Given a binary tree, return a 2-D array with vertical order traversal of it.
SOLUTION
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
public class Solution {
public ArrayList<ArrayList<Integer>> verticalOrderTraversal(TreeNode A) {
TreeNode root = A;
if(root == null) return new ArrayList<ArrayList<Integer>>();
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(root, 0));
Map<Integer, ArrayList<Integer>> map = new HashMap<>();
int minLevel=0;
int maxLevel=0;
while(!q.isEmpty()){
Pair p = q.remove();
TreeNode node = p.node;
int level = p.level;
if(!map.containsKey(level)){
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(node.val);
map.put(level, list);
}else{
map.get(level).add(node.val);
}
if(node.left != null){
q.add(new Pair(node.left, level-1));
minLevel = Math.min(minLevel, level-1);
}
if(node.right != null){
q.add(new Pair(node.right, level+1));
maxLevel = Math.max(maxLevel, level+1);
}
}
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
for(int i=minLevel; i<=maxLevel; i++){
res.add(map.get(i));
}
return res;
}
}
class Pair{
TreeNode node;
int level;
public Pair(TreeNode node, int level){
this.node = node;
this.level = level;
}
}