關于逆序數的問題描述如下：

已知數組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];
nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];

這里我們使用二叉搜索樹實現，可以思考如下：
將nums和count數組都進行逆序，則會有如下結果
nums=[1,-2,5,3,1,9,-7,5],count = [0,0,2,2,1,5,0,5]

此時我們發現，對于nums中的每個元素，只需要確定它的左側比自己小的元素的個數，這樣的結果就可以構造出右側的count。

自然，我們想到了二叉搜索樹的性質，可以畫出如下導圖：

代碼實現如下（文末有完整測試代碼）:

/*二叉樹數據結構，新增count屬性，保存左節點的個數*/
typedef struct tree
{int data;int count;//保存當前節點有多少個左節點struct tree *left;struct tree *right;tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;/*通過二叉樹進行計算*/
void insert(Tree *root, Tree *node, int &small_count) {if (node -> data <= root ->data) {root -> count ++; //當前節點左節點個數累加，因為插入的節點已經比當前節點小了if (root -> left) {insert(root->left,node, small_count);} else {root -> left = node;}} else {/*如果大于當前節點，則說明當前節點的所有左節點包括自己都比插入節點小，進行賦值*/small_count += root -> count + 1; if (root ->right) {insert(root ->right, node, small_count);} else {root -> right = node;}}
}/*獲取最終的逆序數組*/
std::vector<int> get_smaller_numbers(std::vector<int> &arr) {std::vector<int> count; //逆序后的數組std::vector<Tree *> node; //二叉樹節點數組std::vector<int> result; //最終逆序結果的數組Tree *tmp;for (int i  = arr.size() - 1;i >= 0; i--) {node.push_back(new tree(arr[i]));}count.push_back(0);for (int i = 1;i < arr.size(); ++i) {int small_count = 0;insert(node[0],node[i],small_count);count.push_back(small_count);}/*對計算好的結果進行逆序，恢復初始結果*/for (int i = count.size() - 1; i >= 0; --i) {delete node[i];result.push_back(count[i]);}return result;
}

測試代碼如下:

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>using namespace std;
/*二叉樹數據結構*/
typedef struct tree
{int data;int count;//保存當前節點有多少個左節點struct tree *left;struct tree *right;tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;/*通過二叉樹進行計算*/
void insert(Tree *root, Tree *node, int &small_count) {if (node -> data <= root ->data) {root -> count ++;if (root -> left) {insert(root->left,node, small_count);} else {root -> left = node;}} else {small_count += root -> count + 1;if (root ->right) {insert(root ->right, node, small_count);} else {root -> right = node;}}
}std::vector<int> get_smaller_numbers(std::vector<int> &arr) {std::vector<int> count; //逆序后的數組std::vector<Tree *> node; //二叉樹節點數組std::vector<int> result; //最終逆序結果的數組Tree *tmp;for (int i  = arr.size() - 1;i >= 0; i--) {node.push_back(new tree(arr[i]));}count.push_back(0);for (int i = 1;i < arr.size(); ++i) {int small_count = 0;insert(node[0],node[i],small_count);count.push_back(small_count);}/*對計算好的結果進行逆序，恢復初始結果*/for (int i = count.size() - 1; i >= 0; --i) {delete node[i];result.push_back(count[i]);}return result;
}int main(int argc, char const *argv[])
{int test[] = {5,-7,9,1,3,5,-2,1};std::vector<int> num;for (int i = 0;i < 8; ++i) {num.push_back(test[i]);}std::vector<int> result;result = get_smaller_numbers(num);for (int i = 0;i < result.size(); ++i) {cout << "[" << result[i] << "] ";}return 0;
}

輸出結果如下:

[5] [0] [5] [1] [2] [2] [0] [0]

總結

以上是生活随笔為你收集整理的二叉树：二叉搜索树实现 逆序数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。