右侧小于当前元素的个数

问题描述

给定一个整数数组nums[n]。对于所有元素，给出nums[n]中该元素右侧小于该元素的元素个数count[n]。

比如：

  1. 输入: nums[4] = [5,2,6,1]
  3. 输出: count[4] = [2,1,1,0]

求解方法

使用二叉排序树，结点特殊设计一下

BST顺序号

要得到BST中某个结点的排序位次，必须要对树进行遍历。
可以对树结点进行修改，这样不进行遍历也能得到排序位次

Struct BSTNode {
    int value;
    int biggerCount;    // 右子树结点数量
    int smallerCount;   // 左子树结点数量
    BSTNode* lChild;
    BSTNode* rChild;
};

这样修改之后，只需要在查询结点的过程中做一些加减法即可