JAVA 13ms DFS Solution, TreeMap + PriorityQueue

• BFS is simpler for this question. I provide a DFS solution here.
Use the height and insert orders as the key for sorting the queue.

``````public class Solution {
class Ele implements Comparable<Ele>{
int val;
int h;
int order;
Ele(int val, int h, int order){
this.val = val;
this.h = h;
this.order = order;
}
public int compareTo(Ele other){
if(this.h == other.h){
return Integer.compare(this.order, other.order);
}
return Integer.compare(this.h, other.h);
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)return res;
Map<Integer, PriorityQueue<Ele>> map = new TreeMap<>();
preOrder(root, map, 0, 0);
for(Integer key:map.keySet()){
PriorityQueue<Ele> tmp = map.get(key);
List<Integer> tmpList = new ArrayList<Integer>();
while(!tmp.isEmpty()){
tmpList.add(tmp.poll().val);
}
res.add(tmpList);
}
return res;
}
public void preOrder(TreeNode root, Map<Integer, PriorityQueue<Ele>> map, int key, int height){
if(root == null)return;
if(map.containsKey(key)){
PriorityQueue<Ele> tmp = map.get(key);
tmp.add(new Ele(root.val,height,tmp.size()));
}else{
PriorityQueue<Ele> tmp = new PriorityQueue<Ele>();
tmp.add(new Ele(root.val,height,1));
map.put(key, tmp);
}
preOrder(root.left, map, key-1, height+1);
preOrder(root.right, map, key+1, height+1);
}
}
``````

• Did you pass all tests? I got one wrong. I think the expected result is wrong.

for test:
[-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

there's one column, my answer is
[3,-44,-60,12,-51,-59,67,-88,48,-26,92,72]
the expected answer is:
[3,-44,-60,12,-59,-51,67,-88,48,-26,92,72]

• @jobhunting88 I did pass all the tests, otherwise I won't post it. I think there maybe some tiny error in your code. The input order matters (when two nodes the same height), previously I didn't store the order and I failed.

The output from my code:

[[-4,78,73,-77,-54,-36],[12,-51,-81,4,8,3,-30,-33,86,81,98,24],[-64,-53,-31,47,-35,-67,-37,72,-4,-38,-31,-31,-18,-66,-72,43],[18,-93,33,-51,-38,47,-24,-11,80,44,-91,-42,-40,70,-93],[76,3,-64,26,-31,-19,10,-85,-96,67,34,-92,-1],[3,-44,-60,12,-59,-51,67,-88,48,-26,92,72],[53,-81,27,60,-55,-70,72,56,-88,-98,-84],[11,-49,-90,90,-34,-27,-67,98],[74,17,-17,-65,-53,39],[37]]

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