几乎和1020一样，还是要弄清楚建树的问题，是个套路问题
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* left;
node* right;
};
int N;
vector<int> in,pre;
node* create(int preL,int preR,int inL,int inR) //序列区间
{
if(preL>preR)
return NULL;
node* root=new node;
root->data=pre[preL];
int i;
for(i=inL;i<=inR;i++)
if(in[i]==pre[preL])
break;
int numLeft=i-inL;
root->left=create(preL+1,preL+numLeft,inL,i-1);
root->right=create(preL+numLeft+1,preR,i+1,inR);
return root;
}
int num=0;
void postorder(node* root)
{
if(root==NULL)
return;
postorder(root->left);
postorder(root->right);
printf("%d",root->data);
num++;
if(num<N)
printf(" ");
}
int main()
{
scanf("%d",&N);
string op;
int num;
stack<int> st;
getchar();
for(int n=0;n<N*2;n++)
{
getline(cin,op);
if(op.substr(0,4)=="Push")
{
op=op.erase(0,5);
num=atoi(op.c_str());
st.push(num);
pre.push_back(num);
}
else
{
in.push_back(st.top());
st.pop();
}
}
node* root=create(0,N-1,0,N-1);
postorder(root);
return 0;
}
