PAT甲级 1086 Tree Traversals Again 二叉树已知前序、中序求后序
程序员文章站
2022-06-11 15:11:21
...
Solution:
push的顺序即为前序
pop出栈的顺序即为中序
根据前序、中序求后序
代码如下:
//二叉树已知前序、中序求后序
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int pre[35],in[35];
int n;
stack<int> s;
vector<int> post(n);
void post_traversal(int root,int start,int ends){//后序打印
if(start>ends){
return;
}
int i=start;
while(i<ends&&in[i]!=pre[root]){//找到中序序列中根结点的位置
i++;
}
post_traversal(root+1,start,i-1);//遍历左子树
post_traversal(root+1+i-start,i+1,ends);//遍历右子树
post.push_back(pre[root]);
}
int main(){
cin>>n;
string command;
int ans1=0,ans2=0;
int key;
for(int i=0;i<=2*n-1;i++){
cin>>command;
if(command=="Push"){
cin>>key;
pre[ans1++]=key;
s.push(key);
}else if(command=="Pop"){
in[ans2++]=s.top();
s.pop();
}
}
post_traversal(0,0,n-1);
for(int i=0;i<post.size();i++){
if(i!=post.size()-1){
cout<<post[i]<<" ";
}else{
cout<<post[i];
}
}
return 0;
}