315. Count of Smaller Numbers After Self

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        TreeNode *root = NULL;
        for (int i = nums.size() - 1; i >= 0; i--)
            root = helper(root, nums[i], res[i]);
        return res;
    }
private:
    struct TreeNode {
        int val, cnt;   //how many nodes on the left side.
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), cnt(0), left(NULL), right(NULL) {}
    };
    TreeNode* helper(TreeNode* root, int v, int& res) {
        if (root == NULL)
            return (root = new TreeNode(v));
        if (root->val > v) {
            root->cnt++;
            root->left = helper(root->left, v, res);
        } else {
            root->right = helper(root->right, v, res = res + root->cnt + (v == root->val ? 0 : 1));
        }
        return root;
    }
};