右侧更小数

import java.util.*;


public class Solution {
    public ArrayList<Integer> smallerCount1(ArrayList<Integer> nums) {
        // 最大最小取平均数
        int min = nums.get(0);
        int max = nums.get(0);
        for (int num : nums) {
            if (num < min) {
                min = num;
            } else if (num > max) {
                max = num;
            }
        }
        int mid = (min + max) >> 1;

        // 设置根节点
        TreeNode head = new TreeNode(mid);
        head.count = 0;

        for (int i = nums.size() - 1; i >= 0; i--) {
            // 从右向左遍历
            int num = nums.get(i);

            TreeNode par = head; // 每次从根节点出发
            int count = 0; // 计算小于当前数num的值
            while (true) {
                if (num == par.val) {
                    // 当值相等，说明找到了，该节点计数+1
                    par.count = par.count + 1;
                    // count值加上当前节点的leftCount，leftCount每次添加节点的时候左滑计数，如果当前节点是父节点右孩子，代表： 父节点值 < num < 当前节点值
                    count = count + par.leftCount;
                    break;
                } else if (num > par.val) {
                    // 向右滑
                    count = count + par.leftCount +
                            par.count; // 右滑结算当前节点的leftCount与当前节点的数量
                    TreeNode right = par.right;
                    if (right == null) {
                        // 右孩子为空说明到头了，初始化右孩子并且设置为count=1（构造设置）
                        right = new TreeNode(num);
                        par.right = right;
                        break;
                    }
                    // 右孩子不为空，右滑继续
                    par = right;
                } else {
                    // 小于当前节点值，左滑并且leftCount+1
                    par.leftCount = par.leftCount + 1;
                    TreeNode left = par.left;
                    if (left == null) {
                        // 如果没左孩子，初始化左孩子，退出循环
                        left = new TreeNode(num);
                        par.left = left;
                        break;
                    }
                    // 左孩子不为空，继续循环向下
                    par = left;
                }
            }
            // 设置结果
            nums.set(i, count);
        }

        return nums;
    }

    private static class TreeNode {
        private int val;
        private int leftCount;
        private int count;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
            count = 1;
        }
    }
}