#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node *lchild,*rchild;
};
vector<int>pre,in,post;
stack<int>q;
node*create(int preL,int preR,int inL,int inR)
{
if(preL>preR)return NULL;
node*root=new node;
root->data=pre[preL];
int k;
for(k=inL;k<=inR;k++)
{
if(in[k]==root->data)break;
}
int numleft=k-inL;
root->lchild=create(preL+1,preL+numleft,inL,k-1);
root->rchild=create(preL+numleft+1,preR,k+1,inR);
return root;
}
void postorder(node*root)
{
if(root==NULL)return;
postorder(root->lchild);
postorder(root->rchild);
post.push_back(root->data);
}
int n;
int main()
{
scanf("%d",&n);
int k=2*n;
while(k--)
{
getchar();
string s;
int x;
cin>>s;
if(s[1]=='u')
{
scanf("%d",&x);
pre.push_back(x);
q.push(x);
}
else
{
x=q.top();
q.pop();
in.push_back(x);
}
}
node*root=create(0,n-1,0,n-1);
postorder(root);
for(int i=0;i<post.size();i++)
{
printf("%d",post[i]);
if(i!=post.size()-1)printf(" ");
}
return 0;
}
1086 Tree Traversals Again（25 分）
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- (一) 自制力与年龄无关 君不见，当年伽利略，斜塔做实验，大球小球落地同瞬间。又何言，今日自制力，大人小孩不一般？...
