借鑒柳神做法，不用生成樹
7-28 搜尋樹判斷
對于二叉搜尋樹，我們規定任一結點的左子樹僅包含嚴格小于該結點的鍵值，而其右子樹包含大于或等于該結點的鍵值。如果我們交換每個節點的左子樹和右子樹，得到的樹叫做鏡像二叉搜尋樹。
現在我們給出一個整數鍵值序列，請編寫程式判斷該序列是否為某棵二叉搜尋樹或某鏡像二叉搜尋樹的前序周遊序列，如果是，則輸出對應二叉樹的後序周遊序列。
輸入格式:
輸入的第一行包含一個正整數N（≤1000），第二行包含N個整數，為給出的整數鍵值序列，數字間以空格分隔。
輸出格式:
輸出的第一行首先給出判斷結果，如果輸入的序列是某棵二叉搜尋樹或某鏡像二叉搜尋樹的前序周遊序列，則輸出
YES
，否側輸出
NO
。如果判斷結果是
YES
，下一行輸出對應二叉樹的後序周遊序列。數字間以空格分隔，但行尾不能有多餘的空格。
輸入樣例1:
7
8 6 5 7 10 8 11 複制
輸出樣例1:
YES
5 7 6 8 11 10 8 複制
輸入樣例2:
7
8 6 8 5 10 9 11 複制
輸出樣例2:
NO 複制
邊判斷 邊把根存進去。後序周遊方法存入數組。
使用isMirror進行兩次判斷。
用根root 和邊界值尾下标tail進行判斷是否滿足搜尋樹條件。
#include<iostream>
#include<vector>
using namespace std;
vector<int>num;
vector<int>nn;
bool isMirror = false;
void getpose(int root,int tail){
if(root > tail)return;
int i = root+1, j = tail;
if(!isMirror){
while(i <= tail && num[root] > num[i]) i++;
while(j > root && num[root] <= num[j]) j--;
}else{
while(i <= tail && num[root] <= num[i]) i++;
while(j > root && num[root] > num[j]) j--;
}if(i-j != 1)return;
getpose(root+1,j);
getpose(i,tail);
nn.push_back(num[root]);
}
int main(){
int n;
cin>>n;
num.resize(n);
for(int i=0;i<n;i++)cin>>num[i];
getpose(0,n-1);
if(nn.size()!=n){
isMirror = true;
nn.clear();
getpose(0, n-1);
}
if(nn.size() == n){
printf("YES\n%d",nn[0]);
for(int i=1;i<n;i++)cout<<" "<<nn[i];
}else cout<<"NO";
return 0;
} 複制