和刚刚之前的那道题类似，只不过多考察了一个四大遍历输出中的一个；自己跟个智障一样检查了一个小时，结果发现少了一个返回指针，真是干他娘的；
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
using std::vector;
const int maxn=40;
int n;
vector<int>pre;
vector<int>in;
stack<int>s;
struct node{
int data;
node* lchild;
node* rchild;
};
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 lnum=i-inl;
root->lchild=create(prel+1,prel+lnum,inl,i-1);
root->rchild=create(prel+lnum+1,prer,i+1,inr);
return root;
}
int num=0;
void postorder(node* root){
if(root==NULL)
return;
postorder(root->lchild);
postorder(root->rchild);
printf(“%d”,root->data);
num++;
if(num<n)
printf(” “);
}
int main(){
scanf(“%d”,&n);
char str[5];
int x;
for(int i=0;i<2*n;i++){
scanf(“%s”,str);
if(strcmp(str,”Push”)==0){
scanf(“%d”,&x);
pre.push_back(x);
s.push(x);
}else{
in.push_back(s.top());
s.pop();
}
}
node* root=create(0,n-1,0,n-1);
postorder(root);
system(“pause”);
return 0;
}