Java Binary Search Tree solution

• 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;
}
}
``````

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