柳婼代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> pre,post;
//isMirror==0为BST isMirror==1为镜像
void getpost(int root,int tail,int isMirror){
if(root>tail) return;
//lc为前序遍历中左子树部分最后一个元素下标
//rc为前序遍历中右子树部分第一个元素下标
int lc,rc;
lc=tail;
rc=root+1;
//找到左右子树部分在前序遍历中的边界下标
if(!isMirror){
while(lc>root && pre[lc]>=pre[root]) lc--;
while(rc<=tail && pre[rc]<pre[root]) rc++;
}
else{
while(lc>root && pre[lc]<pre[root]) lc--;
while(rc<=tail && pre[rc]>=pre[root]) rc++;
}
if(lc+1!=rc) return;
//对左子树进行递归
getpost(root+1,lc,isMirror);
//对右子树进行递归
getpost(rc,tail,isMirror);
//树的后序遍历
post.push_back(pre[root]);
}
int main(){
int n;
cin>>n;
pre.resize(n);
for(int i=0;i<n;i++) cin>>pre[i];
getpost(0,n-1,0); //先按BST处理
if(post.size()!=n){
post.clear(); //再用时清空
getpost(0,n-1,1);
}
if(post.size()!=n) puts("NO");
else{
cout<<"YES"<<endl;
cout<<post[0];
for(int i=1;i<post.size();i++)
cout<<" "<<post[i];
cout<<endl;
}
return 0;
}
死办法,建树在先序遍历,和原序列进行比较
#include <iostream>
#include <vector>
using namespace std;
//origin初始序列,pre原树先序序列,post原树后序序列,preM镜像树先序,postM镜像树后序
vector<int> origin,pre,post,preM,postM;
struct node{
int data;
node *left,*right;
};
void insert(node* &root,int v){
if(root==NULL){
root=new node;
root->data=v;
root->left=root->right=NULL;
return;
}
if(root->data>v) insert(root->left,v);
else insert(root->right,v);
}
//对原树进行先序遍历
void preorder(node* root,vector<int>& temp){
if(root==NULL) return;
temp.push_back(root->data);
preorder(root->left,temp);
preorder(root->right,temp);
}
//对镜像树进行先序遍历,和原树操作对称
void preorderMirror(node* root,vector<int>& temp){
if(root==NULL) return;
temp.push_back(root->data);
preorderMirror(root->right,temp);
preorderMirror(root->left,temp);
}
//对原树进行后序遍历
void postorder(node* root,vector<int>& temp){
if(root==NULL) return;
postorder(root->left,temp);
postorder(root->right,temp);
temp.push_back(root->data);
}
//对镜像树进行后序遍历,和原树操作对称
void postorderMirror(node* root,vector<int>& temp){
if(root==NULL) return;
postorderMirror(root->right,temp);
postorderMirror(root->left,temp);
temp.push_back(root->data);
}
int main(){
int n;
cin>>n;
node* root=NULL;
for(int i=0;i<n;i++){
int value;
cin>>value;
insert(root,value);
origin.push_back(value);
}
preorder(root,pre);
preorderMirror(root,preM);
postorder(root,post);
postorderMirror(root,postM);
if(pre==origin){ //初始序列等于先序序列
cout<<"YES"<<endl;
cout<<post[0];
for(int i=1;i<n;i++) cout<<" "<<post[i];
cout<<endl;
}
else if(preM==origin){ //初始序列等于镜像树先序序列
cout<<"YES"<<endl;
cout<<postM[0];
for(int i=1;i<n;i++) cout<<" "<<postM[i];
cout<<endl;
}
else cout<<"NO"<<endl;
return 0;
}