数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告