題目來源：團體程序設計天梯賽-練習集
題目地址：L2-004 這是二叉搜索樹嗎？

題目大意

給定一個長度為 $n$ 的序列，判斷這是否是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果。如果是，則在一行中輸出 YES ，然后在下一行輸出該樹后序遍歷的結果，否者直接輸出 NO。

題目分析

1. 預備知識
前序遍歷：先訪問根節點，再遍歷左子樹，最后遍歷右子樹。

后序遍歷：先遍歷左子樹，再遍歷右子樹，最后訪問根節點。
（注意：遍歷子樹的時候也要按照相應的的方式遍歷。）

二叉搜索樹的基本性質（如題目描述所示）

2. 結題要義
首先，我們假設輸入的序列 $a[]$ 就是一棵二叉搜索樹進行前序遍歷的結果，$l$ 和 $r$ 分別為序列 $a[]$ 的左右邊界。

根據前序遍歷的性質，我們可以知道 $a[l]$ 即為這棵樹的根節點、 $l+1$ 為左子樹的左邊界， $r$ 為右子樹的右邊界。然后我們定義兩個指針 $tl$ 、$tr$ 分別表示右子樹的左邊界、左子樹的右邊界。（注意哪個對應哪個）

初始化 $tl=l+1$ 、$tr=r$，接著根據二叉樹搜索樹的性質 ，$tl$ 往右移動，找到第一個大于或等于根節點 $a[l]$ 的節點、$tr$往右移動，找到第一個小于根節點 $a[l]$ 的節點。過程如下圖所示，

這樣就確定了序列中根節點、左子樹和右子樹的位置，我們遞歸進行這個這個過程，就可以得到整棵樹的結構，過程如下圖所示：

為了簡便，我們可以省去建樹的過程，在確定了序列中根節點、左子樹和右子樹的位置后，就直接進行后序遍歷。由確定子樹范圍的過程可得，若這是一顆二叉搜索樹，則必有 $tl?tr=1$ ，要是不滿足這個條件，我們就直接停止遍歷。

訪問根節點時，我們可以將根節點放入 $vector$ 中（$vector$即為后序遍歷序列）。最后我們通過判斷 $vector$ 中的元素個數是否等于 $n$ 來判斷這是否為二叉搜索樹。

如果等于 $n$ ，就可以輸出 $vector$ ；否則就判斷是否為鏡像。至于求判斷鏡像的過程也基本和上訴無異，區別在于確定子樹范圍的條件而已。

代碼如下

#include <bits/stdc++.h>using namespace std; const int maxn = 1e3 + 10; int n, flag; /*** a[]用于存儲輸入的前序遍歷序列* ans用于存儲后序遍歷的結果*/ int a[maxn]; vector<int> ans;/*** 后序遍歷這顆二叉樹**/ void dfs(int l, int r) {if (l > r) return ;//tl表示右子樹的左邊界，tr表示左子樹的右邊界int tl = l + 1, tr = r;if (flag) {//判斷二叉搜索樹的“鏡像”while (tl <= r && a[tl] >= a[l]) tl++;while (tr > l && a[tr] < a[l]) tr--;} else {//判斷二叉搜索樹while (tl <= r && a[tl] < a[l]) tl++;while (tr > l && a[tr] >= a[l]) tr--;}//不滿足二叉搜索樹的條件if (tl - tr != 1) return ;//訪問左子樹dfs(l + 1, tr);//訪問右子樹dfs(tl, r);//訪問根節點ans.push_back(a[l]); }int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];//先檢查是不是二叉搜索樹的“鏡像”dfs(1, n);//如果不滿足，則再檢查是不是二叉搜索樹if (ans.size() != n) {flag = 1;ans.clear();dfs(1, n);}if (ans.size() != n) {cout << "NO" << endl;} else {cout << "YES" << endl;for (int i = 0; i < n; i++) {cout << ans[i] << (i == n -1 ? '\n' : ' ');}}return 0; }

---

如果本文對你有所幫助，記得點個贊哦~

總結

以上是生活随笔為你收集整理的L2-004 这是二叉搜索树吗？-团体程序设计天梯赛GPLT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。