Queue Reconstruction by Height - Teeeeeebag/LeetCode GitHub Wiki

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