# Untitled

unknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
```class Node{
int val;
Node left;
Node right;
Node(int v, Node l, Node r){
val = v;
left = l;
right = r;
}
}

class Solution {
public ArrayList<Integer> order(ArrayList<Integer> A, ArrayList<Integer> B) {
Map<Integer, Integer> hm = new HashMap<>();
int n = A.size();
for(int i = 0; i < n; i++){
hm.put(A.get(i), B.get(i));
}
Collections.sort(A, Collections.reverseOrder());
Node head = null;
for(int i: A){
head = addToTheLL(head, i, hm.get(i));
}
return getListFromLL(head);

}

Node addToTheLL(Node head, int value, int h){
if(head == null){
return new Node(value, null, null);
}
Node rootLeft = null;
Node root = head;
while(h --> 0){
rootLeft = root;
root = root.right;
}
if(rootLeft == null){
return addToHead(head, root, value);
}
else if(root == null){
return addToEnd(head, rootLeft, value);
}
else{
return addInMiddle(head, root.left, root, value);
}
}

Node addToHead(Node head, Node root, int val){
root.left = new Node(val, null, root);
return root.left;
}

Node addToEnd(Node head, Node root, int val){
root.right = new Node(val, root, null);
return head;
}

Node addInMiddle(Node head, Node root, Node rootRight, int val){
Node valNode = new Node(val, root, rootRight);
root.right = valNode;
rootRight.left = valNode;
return head;
}

ArrayList<Integer> getListFromLL(Node head){
ArrayList<Integer> lst = new ArrayList<>();
while(head != null){
lst.add(head.val);
head = head.right;
}
return lst;
}
}
```
Leave a Comment