315. Count of Smaller Numbers Af

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

一刷
题解：Binary Search Tree
For example, [3, 2, 2, 6, 1],
从末尾到头部构造成

                   1(0, 1)
                     \
                     6(3, 1)
                     /
                   2(0, 2)
                       \
                        3(0, 1)

                   1(0, 1)
                   /       \
              2(0, 2)     6(1, 1)
                            /
                          3(0, 1)

题解：每个node有三个域，val, sum, dup(duplicate)
其中sum记录了node的左子树的节点数目。如果num[i]>node.val, 那么继续去右子树寻找，并且结果中可以加上node.sum

class Solution {
    class Node{
        Node left;
        Node right;
        int sum, val, dup = 1;
        public Node(int val, int sum){
            this.val = val;
            this.sum = sum;
        }
    }
    
    
    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        Node root = null;
        for(int i=nums.length-1; i>=0; i--){
            root = insert(nums[i], res, i, root, 0);
        }
        return Arrays.asList(res);
    }
    
    private Node insert(int val, Integer[] res, int i, Node cur, int preSum){
        if(cur == null){
            cur = new Node(val, 0);
            res[i] = preSum;
        }else if(cur.val == val){
            cur.dup++;
            res[i] = preSum + cur.sum;
        }else if(cur.val>val){
            cur.sum++;
            cur.left = insert(val, res, i, cur.left, preSum);
        }else if(cur.val < val){
            cur.right = insert(val, res, i, cur.right, preSum + cur.dup + cur.sum);
        }
        return cur;
        
    }
}

二刷
二叉搜索树。
Node有三个域，val, leftSum(左子树node数目), dup(重复点的数目)
如果插入到左边，当前cur.leftSum++
如果插入到右边，总的sum+= cur.leftSum+dup
如果相等, cur.dup++, res[index] = preSum + cur.leftSum

class Solution {
    class Node{
        Node left, right;
        int val, leftSum, dup = 1;
        Node(int val, int leftSum){
            this.val = val;
            this.leftSum = leftSum;
        }
    }
    
    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        Node root = null;
        for(int i=nums.length-1; i>=0; i--){
            root = insert(root, nums[i], i, 0, res);
        }
        return Arrays.asList(res);
    }
    
    private Node insert(Node cur, int val, int index, int preSum, Integer[] res){
        if(cur == null){
            cur = new Node(val, 0);
            res[index] = preSum;;//update
        }else if(cur.val>val){
            cur.leftSum++;
            cur.left = insert(cur.left, val, index, preSum, res);
        }else if(cur.val == val){
            cur.dup++;
            res[index] = preSum+cur.leftSum;//update
        }else{
             cur.right = insert(cur.right, val, index, preSum+cur.leftSum+cur.dup, res);
        }
        return cur;
    }
}