I'm trying to solve this exercise and here's my solution. It basically holds a tree map to map the nodes at the same veritical offset to a key. And uses a priority queue to split ties when there are multiple keys at the same (horizontal level) using the value at the node.
public List<List<Integer>> verticalTraversal(TreeNode root) {
Map<Integer, PriorityQueue<Node>> map = new TreeMap<>();
List<List<Integer>> out = new ArrayList<>();
if(root == null)
return out;
Queue<Node> q = new LinkedList<>();
Node r = new Node(root, 0, 0);
q.add(r);
while(!q.isEmpty()) {
Node curr = q.remove();
int x = curr.x;
int y = curr.y;
PriorityQueue<Node> pq = map.getOrDefault(y, new PriorityQueue<Node>((a,b) ->(a.x == b.x? a.t.val - b.t.val: a.x - b.x)));
pq.add(curr);
map.put(y,pq);
if(curr.t.left!=null){
Node left = new Node(curr.t.left, x+1, y-1);
q.add(left);
}
if(curr.t.right!=null){
Node right = new Node(curr.t.right, x+1, y + 1);
q.add(right);
}
}
for (Map.Entry<Integer, PriorityQueue<Node>> entry : map.entrySet()){
PriorityQueue<Node> pq = entry.getValue();
List<Integer> vals = new ArrayList<>();
for (Node pqNode: pq){
vals.add(pqNode.t.val);
}
out.add(new ArrayList<Integer>(vals));
}
return out;
}
class Node {
TreeNode t;
int y;
int x;
Node(TreeNode t, int x, int y) {
this.t = t;
this.x = x;
this.y = y;
}
}
}
And to be clear here's where I think the problem is
PriorityQueue<Node> pq = map.getOrDefault(y, new PriorityQueue<Node>((a,b) ->(a.x == b.x? a.t.val - b.t.val: a.x - b.x)));
I get the expected order when a.x
isnt equal to b.x
but it doesnt seem to go by the val
when they're equal.
Here's the failing test case Actual : [[7,9],[5,6],[0,2,4],[1,3],[8]] Expected: [[9,7],[5,6],[0,2,4],[1,3],[8]]
PriorityQueue. comparator() method shares an important function of setting and returning the comparator that can be used to order the elements in a PriorityQueue. The method returns a null value if the queue follows the natural ordering pattern of the elements.
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator. comparator - the comparator that will be used to order this priority queue. If null , the natural ordering of the elements will be used.
In Java, Priority Queue, by default implement min Priority Queue, If we need to change the order of Priority Queue from min to max Priority Queue, then we use some methods as follows: Using default Comparator Collections. reverseOrder() Using custom Comparator.
Parameters: capacity - the initial capacity for this priority queue comparator - the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used. public PriorityQueue(SortedSet ss) : Creates a PriorityQueue containing the elements in the specified sorted set.
What your doing wrong is that you iterate over the elements of the priority queue instead of polling it.
The documentation of PriorityQueue#iterator() clearly states:
Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.
Instead of writing
for (Node pqNode: pq){
vals.add(pqNode.t.val);
}
you should use:
Node pqNode;
while ((pqNode = pq.poll()) != null) {
vals.add(pqNode.t.val);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With