資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告