資料結構
網路
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 次瀏覽
廣告