# Java Straight forward solution with a designed data structure

• I design a data structure BigNode to keep record of both nodes and its relative position in the result. With BFSing the given tree, I can summary the structure and write it to a TreeMap(the reason for using TreeMap is it can sort the input automatically). In the end, what I only need to do it transfer every key-value pair in TreeMap to the result ArrayList;
(I also write a print function to help you debug the program with the RunCode function)

``````class BigNode{
TreeNode node;
int pos;
BigNode(TreeNode node, int pos){
this.node = node;
this.pos = pos;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;

BigNode node = new BigNode(root, 0);
TreeMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();

queue.offer(node);
while(!queue.isEmpty()){
int levelNum = queue.size();
for(int i = 0; i < levelNum; i ++){
BigNode tmp = queue.peek();
if(queue.peek().node.left != null){
BigNode left = new BigNode(tmp.node.left, tmp.pos - 1);
queue.offer(left);
}
if(queue.peek().node.right != null){
BigNode right = new BigNode(tmp.node.right, tmp.pos + 1);
queue.offer(right);
}
if(map.containsKey(queue.peek().pos)){
}else{
List<Integer> cur = new ArrayList<Integer>();
map.put(queue.peek().pos, cur);
}
queue.poll();
}
}
print(map);

for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
}
return res;
}
/*
public void print(TreeMap<Integer, List<Integer>> map){
for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
int key = entry.getKey();
List<Integer> value = entry.getValue();
System.out.print(key + "      ");
for(int val : value){
System.out.print(val + " ");
}
System.out.println();
}
System.out.println();
}
*/
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.