315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property wherecounts[i]is the number of smaller elements to the right ofnums[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].

S1: binary search tree O(n*logn) best O(n^n) worst

从后往前建立BST，在每个节点记录该节点左子树node个数（包括他自己）为leftCount，每次insert一个节点时，从root开始将每次右拐node的leftCount相加即为该节点的count

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        if (n == 0) return result;
        Node* root = new Node(nums[n - 1], 1);
        for (int i = n - 2; i >= 0; --i) {
            result[i] = insertNode(root, nums[i], 0);
        }
        return result;
    }

private:
    struct Node{
        int val;
        int leftCount;
        Node* left;
        Node* right;
        Node(int a, int b) : val(a), leftCount(b) {}
    };

    int insertNode(Node* root, int val, int count) {
        if (root->val >= val) {
            root->leftCount++;
            if (root->left) {
                return insertNode(root->left, val, count);
            } else {
                root->left = new Node(val, 1);
                return count;
            }
        } else {
            count += root->leftCount;
            if (root->right) {
                return insertNode(root->right, val, count);
            } else {
                root->right = new Node(val, 1);
                return count;
            }
        }
    }
};