目錄
1，題目描述
題目大意
2，思路
方法一：
方法二（柳神）：
3，代碼
方法一：
方法二：
1，題目描述
Sample Input 1:
7
8 6 5 7 10 8 11 Sample Output 1:
YES
5 7 6 8 11 10 8 Sample Input 2:
7
8 10 11 8 6 7 5 Sample Output 2:
YES
11 8 10 7 5 6 8 Sample Input 3:
7
8 6 8 5 10 9 11 Sample Output 3:
NO 題目大意
給出樹的節點數，以及一系列值，判斷這些值是不是二叉搜尋樹（或者是該樹的鏡像）的先序周遊，是則輸出Yes，并輸出其後序周遊；
2，思路
方法一：
極為野蠻的解法。先建構BST，并求出先序周遊pre和鏡像先序周遊preMir，對照輸入是否為其中一個；
若是，則求後序周遊/鏡像後序周遊；
否則，輸出NO；
方法二（柳神）：
充分利用鏡像BST的特點：
- 左子樹的值小于目前節點，右子樹的值大于等于目前節點；
- BST的先序周遊，隻要是值小于根節點root的都是左子樹上的點，否則就是右子樹上的點。據此可以判斷左右兩子樹的根節點，并遞歸的周遊左右兩子樹；
如圖。紅色表示根節點，不同顔色表示不同的樹（為了區分，根節點未填充）
根據輸入的序列，可以判斷左子樹的根節點（root後一個位置），右子樹根節點（從root向tail周遊，第一個大于root對應值的節點）。遞歸地進行其他子樹的周遊（getpost(root + 1, j)；getpost(i, tail)；），并在最後将root存入後序周遊的序列中即可（post.push_back(pre[root])；）。
最後隻需要判斷post.size()是否為n（每個節點均周遊過），即可判斷輸入是否為先序序列。
鏡像輸入的話也一樣。
3，代碼
方法一：
#include<iostream>
#include<vector>
using namespace std;
vector<int> input, pre, preMir, ans; //input輸入數組 pre先序周遊 preMir鏡像先序周遊
struct tree{
int key;
tree * left = NULL;
tree * right = NULL;
};
void insert(tree *& node, int key){ //建構BST 注意加&
if(node == NULL){
node = new tree;
node->key = key;
}else{
if(key < node->key)
insert(node->left, key);
else
insert(node->right, key);
}
}
void preOrder(tree * node){ //先序周遊
if(node != NULL){
pre.push_back(node->key);
preOrder(node->left);
preOrder(node->right);
}
}
void preMirOrder(tree * node){ //鏡像先序周遊
if(node != NULL){
preMir.push_back(node->key);
preMirOrder(node->right);
preMirOrder(node->left);
}
}
void postOrder(tree * node){ //後序周遊
if(node != NULL){
postOrder(node->left);
postOrder(node->right);
ans.push_back(node->key);
}
}
void postMirOrder(tree * node){ //鏡像後序周遊
if(node != NULL){
postMirOrder(node->right);
postMirOrder(node->left);
ans.push_back(node->key);
}
}
int main(){
//#ifdef ONLINE_JUDGE
//#else
// freopen("1.txt", "r", stdin);
//#endif
int n;
cin>>n;
tree * root = NULL;
int key, i;
for(i = 0; i < n; i++){
cin>>key;
input.push_back(key);
insert(root, key);
}
preOrder(root);
preMirOrder(root);
i = 0;
while(i < n){
if(pre[i] == input[i])
i++;
else
break;
}
if(i < n){ //若不是正常的先序周遊 判斷是否為鏡像先序周遊
i = 0;
while(i < n){
if(preMir[i] == input[i])
i++;
else
break;
}
if(i < n){ //既不是正常的先序周遊 也不是鏡像先序周遊
cout<<"NO";
return 0;
}
postMirOrder(root);
}else postOrder(root);
cout<<"YES"<<endl<<ans[0];
for(i = 1; i < n; i++){
cout<<' '<<ans[i];
}
return 0;
} 方法二：
#include<iostream>
#include<vector>
using namespace std;
bool isMirror;
vector<int> pre, post;
void getPost(int root, int tail){
if(root > tail) return;
int i = root + 1, j = tail;
if(isMirror == false){
while(i <= tail && pre[i] < pre[root]) i++;
while(j > root && pre[j] >= pre[root]) j--;
}else{
while(i <= tail && pre[i] >= pre[root]) i++;
while(j > root && pre[j] < pre[root]) j--;
}
if(i - j != 1) return; //正常情況下i-j應等于1!!!(若不符合先序周遊 那麼post的長度就會小于n)
getPost(root + 1, j); //周遊左子樹
getPost(i, tail); //周遊右子樹
post.push_back(pre[root]); //後序周遊 最後将根節點入棧
}
int main(){
//#ifdef ONLINE_JUDGE
//#else
// freopen("1.txt", "r", stdin);
//#endif
int n;
cin>>n;
int num;
for(int i = 0; i < n; i++){
scanf("%d", &num);
pre.push_back(num);
}
getPost(0, n-1);
if(post.size() != n){
isMirror = true;
post.clear();
getPost(0, n-1);
}
if(post.size() != n){
cout<<"NO";
return 0;
}
cout<<"YES"<<endl<<post[0];
for(int i = 1; i < n; i++)
cout<<' '<<post[i];
return 0;
}