資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 中的 BST 的先序遍歷求出比根結點小的元素的數量
給定先序遍歷的結果，你需要找出比根結點小的元素數量。
先序遍歷中的第一個元素是 BST 的根結點。我們來看一個例子。
輸入
preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]
輸出
3
比根結點小的元素有三個，根結點是 5。
演算法
初始化陣列中的先序結果。
儲存第一個元素，即 BST 的根結點，到某個變數中。
編寫一個迴圈從先序結果的第二個元素開始迭代。
將每個元素與根結點進行比較。
如果當前元素大於根結點，則增加計數。
返回計數。
實現
以下是該演算法在 C++ 中的實現
#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
if (n < 0) {
return 0;
}
int i, root = arr[0], count = 0;
for(i = 1; i < n; i++) {
if(arr[i] < root) {
count += 1;
}
}
return count;
}
int main() {
int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
int n = 8;
cout << getElementsCount(preorder, n) << endl;
return 0;
}輸出
如果你執行上面的程式碼，你將得到以下結果。
3
更新於： 26-10-2021
71 次瀏覽
廣告