資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定大小為 n 的陣列是否可以表示 C++ 中 n 層的 BST
我們有一個數組 A，我們必須檢查該陣列是否可以表示具有 n 層的 BST。由於層級是，我們可以按照以下方式構建樹。假設一個數字是 k，大於 k 的值移動到右側，小於 k 的值移動到左側。假設有兩個列表：{50, 20, 9, 25, 10} 和 {50, 30, 20, 25, 10}
第一個無效，但第二個有效。
要檢查這一點，我們可以建立 BST 並檢查高度，或者使用基於陣列的方法。基於陣列的方法如下所示：
- 取兩個變數 max = 無限大，以標記左子樹的最大限制，以及 min = 負無限大以標記右子樹的最小限制
- 對於 arr[i] 到 arr[n – 1] 範圍內的每個元素，重複以下步驟
- 如果 arr[i] > arr[i - 1] 且 arr[i] > min 且 arr[i] < max，則更新 min := arr[i – 1]
- 否則，如果 arr[i] > min 且 arr[i] < max，則更新 max := arr[i]
- 如果這些都不有效，則元素將插入到新級別，因此中斷
示例
#include <iostream>
using namespace std;
bool canMakeBSTifHeightN(int arr[], int n) {
int min = INT_MIN;
int max = INT_MAX;
for(int i = 1; i < n; i++){
if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
min = arr[i - 1];
} else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] <
max) {
max = arr[i - 1];
} else {
return true;
}
}
return false;
}
int main() {
int elements[] = {50, 30, 20, 25, 10};
int n = sizeof(elements)/sizeof(elements[0]);
if (canMakeBSTifHeightN(elements, n))
cout << "We can make BST of height " << n;
else
cout << "We can not make BST of height " << n;
}輸出
We can make BST of height 5
更新於： 2019-10-21
52 次檢視
廣告