Java Binary Search Tree solution


  • 1
    T

    Sort the people array in descending order based on height. If two people have the same height, sort them based on the count. Then insert each people into a BST. leCnt in the tree is used to track the number of nodes in its left subtree including itself.
    Time complexity: O(n^2) if the tree is not balanced, in average it should be n(logn)

    class TreeNode{
        public TreeNode left, right;
        public int[] person;
        public int leCnt; //less than or equal count in the tree
        public int cnt; //greater than or equal to current height, initialize with people[i][1]
        public TreeNode(int[] p, int c){
            person = p;
            cnt = c;
            leCnt = 1;
        }
    }
    public class Solution {
        private TreeNode root = null;
        private void insert(TreeNode n, TreeNode candidate){
            if(n == null){
                root = candidate;
                return;
            }
            if(candidate.cnt - n.leCnt >=0){
                candidate.cnt -= n.leCnt;
                if(n.right == null){
                    n.right = candidate;
                } else {
                    insert(n.right, candidate);
                }
            } else {
                n.leCnt++;
                if(n.left == null){
                    n.left = candidate;
                } else {
                    insert(n.left, candidate);
                }
            }
        }
        private void inorder(TreeNode n, int[][] queue, int[] pos){
            if(n == null){
                return;
            }
            inorder(n.left, queue, pos);
            queue[pos[0]] = n.person;
            pos[0]++;
            inorder(n.right, queue, pos);
        }
        public int[][] reconstructQueue(int[][] people) {
            if(people.length < 2){
                return people;
            }
            int[][] queue = new int[people.length][people[0].length];
            Arrays.sort(people, (a, b) -> {
               if (a[0] == b[0]){
                   return a[1] - b[1];
               } else {
                   return b[0] - a[0];
               }
            });
            for (int[] person : people){
                TreeNode candidate = new TreeNode(person, person[1]);
                insert(root, candidate);
            }
            int[] pos = new int[1];
            inorder(root, queue, pos);
            return queue;
        }
    }
    

Log in to reply
 

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