Untitled
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