已知数组nums,求新数组count，count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。
例如：
nums = [5,2,6,1], count = [2,1,1,0]
nums = [6,6,6,1,1,1], count = [3,3,3,0,0,0]

class Solution{
public:
    std::vector<int> countSmaller(std::vector<int> & nums){}
} ;

LeetCode 315

思考与分析

已知数组nums = [5,-7,9,1,3,5,-2,1],它的逆序数组count = [5,0,5,1,2,2,0,0];数组count[i],为nums[i+1],nums[i+2],...,nums[size()-1]有多少个比nums[i]小的数
或者将数组逆置[1,-2,5,3,1,9,-7,5]
数组count[i]为nums[0]，nums[1],...,nums[i-1]中有多少个比nusm[i]小的个数：
1，数组[]中比它小的个数为0；
-2，数组[1]中比它个小的数为0；
5，数组[1,-2]中比它小的个数为2；
3，数组[1,-2,5]中比它小的个数为2；
。。。
思考：将元素按照原数组逆置后的顺序插入到二叉树查找树中，如何在元素插入时，计算已有多少个元素比当前插入元素小？

struct BSTNode{
    int val;
    int count;
    BSTNode *left;
    BSTNode *right;
    BSTNode (int x) : val(x), left(NULL),right(NULL),count(0){}
};

在插入节点时，当待插入节点insert_node 小于等于当前node时，count++
按照[1,-2,5,3,1,9,-7,5]的顺序构建二叉查找树。

算法思路

将元素按住逆置后的顺序插入到二叉查找树中，如何在元素插入时，计算已有多少个元素比当前插入元素小？
5，[1,-2,5,3,1,9,-7]中比它小的数个数为5.
算法如下：
设置变量count_small = 0 ,记录在插入过程中有多少个元素比插入节点值小；
若待插入节点值小于等于当前节点node值，node->count++,递归将该节点插入到当前节点左子树；
若待插入节点值大于当前节点node值，count_small + = node->count + 1;(当前节点左子树数量+1)，递归将该节点插入到当前节点右子树。

struct BSTNode{
    int val;
    int count;//二叉树左子树中节点个数
    BSTNode *left;
    BSTNode * right;
    BSTNode(int x) : val(x), left(NULL), right(NULL), count(0){}
};

void BST_insert(BSTNode *node, BSTNode * insert_node, int &count_small){
    if(inser_node->val < node->val){
        node->count++;
        if(node->left){
            BST_insert(node->left, insert_node, count_small);
        }
        else{
            node->left = insert_node;
        }
    }
    else{
        count_small + = node->count +1;
        if(node->rifht){
            BST_insert(node->right, insert_node, count_small);
        }
        else{
            node->right = insert_node;
        }
    }
}