数据结构
网络
关系数据库管理系统
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中检查给定数组是否可以表示二叉搜索树的前序遍历
假设数组中有一组元素，我们要检查这些元素是否能表示二叉搜索树的前序遍历。假设一个序列类似于 {40，30，35，80，100}，那么该树将类似于 −
我们可以使用栈来解决这个问题。我们需要按照以下步骤来解决这个问题。
- 定义空栈
- 将根设为负无穷大
- 对前序序列中的每个元素执行以下操作 −
- 如果元素小于当前根，则返回 false
- 在元素大于栈顶时，继续从栈中移除元素，并将最后移除的元素作为根。
- 将元素压入栈中
示例
#include <iostream>
#include <stack>
using namespace std;
bool isValidPreorder(int pre[], int n) {
stack<int> stk;
int root = INT_MIN;
for (int i=0; i<n; i++) {
if (pre[i] < root)
return false;
while (!stk.empty() && stk.top()<pre[i]) {
root = stk.top();
stk.pop();
}
stk.push(pre[i]);
}
return true;
}
int main() {
int pre[] = {40, 30, 35, 80, 100};
int n = sizeof(pre)/sizeof(pre[0]);
if(isValidPreorder(pre, n))
cout << "This can form BST";
else
cout << "This can not form BST";
}输出
This can form BST
更新日期：2019-10-22
469 次浏览
广告