天梯 L2 這是二叉搜索樹嗎？

L2-004?這是二叉搜索樹嗎？?（25 分）

一棵二叉搜索樹可被遞歸地定義為具有下列性質的二叉樹：對于任一結點，

• 其左子樹中所有結點的鍵值小于該結點的鍵值；
• 其右子樹中所有結點的鍵值大于等于該結點的鍵值；
• 其左右子樹都是二叉搜索樹。

所謂二叉搜索樹的“鏡像”，即將所有結點的左右子樹對換位置后所得到的樹。

給定一個整數鍵值序列，現請你編寫程序，判斷這是否是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果。

輸入格式：

輸入的第一行給出正整數?N（≤1000）。隨后一行給出?N?個整數鍵值，其間以空格分隔。

輸出格式：

如果輸入序列是對一棵二叉搜索樹或其鏡像進行前序遍歷的結果，則首先在一行中輸出?YES?，然后在下一行輸出該樹后序遍歷的結果。數字間有 1 個空格，一行的首尾不得有多余空格。若答案是否，則輸出?NO。

輸入樣例 1：

7
8 6 5 7 10 8 11

輸出樣例 1：

YES
5 7 6 8 11 10 8

輸入樣例 2：

7
8 10 11 8 6 7 5

輸出樣例 2：

YES
11 8 10 7 5 6 8

輸入樣例 3：

7
8 6 8 5 10 9 11

輸出樣例 3：

NO



解題思路：
　　先根據題目要求判斷該序列是否是二叉搜索樹或其鏡像進行前序遍歷的結果：
　　判斷[l,r]范圍是否前一部分均小于a[l]，剩下的均大于等于a[l] 或相反。
　　在判斷的過程中我們可以得到這棵樹的左子樹、右子樹和根，所以我們只需在判斷的過程中將其按后序遍歷的順序存下來即可。

#include<bits/stdc++.h>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 1000+5;
const int INF = 0x3f3f3f3f;
int a[N];
vector<int> rt;
void judge(int l,int r,int f){if (l==r) {rt.push_back(a[l]);return ;}int l1=l+1,r1=r;if (!f){while(l1<=r&&a[l1]<a[l]) l1++;while(r1>l&&a[r1]>=a[l]) r1--;}else {while(l1<=r&&a[l1]>=a[l]) l1++;while(r1>l&&a[r1]<a[l]) r1--;}if (l1-r1!=1) return ;judge(l+1,r1,f);judge(l1,r,f);rt.push_back(a[l]);}
int main(){int n;scanf("%d",&n);for (int i=0;i<n;i++) scanf("%d",&a[i]);judge(0,n-1,0);if (rt.size()==n) {printf("YES\n%d",rt[0]);for (int i=1;i<n;i++)printf(" %d",rt[i]);}else {rt.clear();judge(0,n-1,1);if (rt.size()==n) {printf("YES\n%d",rt[0]);for (int i=1;i<n;i++)printf(" %d",rt[i]);}else printf("NO\n");}return 0;
}

?

?