数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 C++ 中验证二叉搜索树中的先序序列
假设我们有一系列数字；我们必须检查它是否是一个二叉搜索树的正确先序遍历序列。我们可以假设序列中的每个数字都是唯一的。考虑以下二叉搜索树 −
因此，如果输入类似于 [5,2,1,3,6]，则输出将为 true
为解决此问题，我们将遵循以下步骤 −
itr := -1
low := -infinity
for 初始化 i := 0，当 i < 先序的大小，更新（将 i 增加 1），执行 −
x := preorder[i]
if x < low，则 −
返回 false
while (itr >= 0 and preorder[itr] < x)，执行 −
low := preorder[itr]
（将 itr 减少 1）
（将 itr 增加 1）
preorder[itr] := x
返回 true
示例
让我们来看以下实现以加深理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool verifyPreorder(vector<int<& preorder) {
int itr = -1;
int low = INT_MIN;
for (int i = 0; i < preorder.size(); i++) {
int x = preorder[i];
if (x < low)
return false;
while (itr >= 0 && preorder[itr] < x) {
low = preorder[itr];
itr--;
}
itr++;
preorder[itr] = x;
}
return true;
}
};
main(){
Solution ob;
vector<int< v = {5,2,1,3,6};
cout << (ob.verifyPreorder(v));
}输入
{5,2,1,3,6}输出
1
更新于： 18-11-2020
111 次浏览
广告