逆序数(二叉查找树)
已知数组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){}
} ;思考与分析
已知数组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;
}
}
}腾讯云开发者
