本文主要是介绍PAT 1086，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//当你真的专注时，环境就不会影响到你。//永远不要当分母
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;const int maxn=40;
stack<int> s;
vector<int> op;
int pre[maxn],in[maxn];
int preL,preR,inL,inR;struct node
{node* lchild;node* rchild;int data;
};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->lchild=create(preL+1,preL+numleft,inL,i-1);root->rchild=create(preL+numleft+1,preR,i+1,inR);return root;
}/*void level_traverse(node* root)
{queue<node*> q;q.push(root);while(!q.empty()){node* top=q.front();q.pop();op.push_back(top->data);if(top->lchild!=NULL)q.push(top->lchild);if(top->rchild!=NULL)q.push(top->rchild);}
}*/void postorder(node* root)
{if(root==NULL)return;postorder(root->lchild);postorder(root->rchild);op.push_back(root->data);
}
int main()
{int n;char str[5];int j=0,k=0;int temp;scanf("%d",&n); for(int i=0;i<2*n;i++){scanf("%s",str);if(strcmp(str,"Push")==0){scanf("%d",&temp);pre[j++]=temp;s.push(temp);}else {in[k++]=s.top();s.pop();}}node* root=create(0,n-1,0,n-1);postorder(root);for(int i=0;i<op.size()-1;i++){printf("%d ",op[i]);}printf("%d",op[op.size()-1]);system("pause");return 0;
}这篇关于PAT 1086的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
