PAT 1129

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<stack> using namespace std; const int maxn=50; struct Node { Node* lchild; Node* rchild; int data; int layer; }; int n; int num=0; int post[maxn],in[maxn]; vector<int> s; stack<Node*> a; Node* create(int inL,int inR,int postL,int postR) { if(postL>postR) return NULL; Node* root=new Node; root->lchild=root->rchild=NULL; root->data=post[postR]; root->layer=0; int k; for(k=inL;k<inR;k++) { if(in[k]==post[postR]) break; } int numleft=k-inL; root->lchild=create(inL,k-1,postL,postL+numleft-1); root->rchild=create(k+1,inR,postL+numleft,postR-1); return root; } void levelorder(Node* root) { if(root==NULL) return; queue<Node*> q; q.push(root); while(!q.empty()) { Node* top=q.front(); q.pop(); s.push_back(top->data); if(top->layer%2!=0) { if(top->lchild!=NULL) { q.push(top->lchild); top->lchild->layer=top->layer+1; } if(top->rchild!=NULL) { q.push(top->rchild); top->rchild->layer=top->layer+1; } } else { if(top->rchild!=NULL) { q.push(top->rchild); top->rchild->layer=top->layer+1; } if(top->lchild!=NULL) { q.push(top->lchild); top->lchild->layer=top->layer+1; } } if(!q.empty()&&q.front()->layer!=top->layer) { while(!q.empty()) { a.push(q.front()); q.pop(); } while(!a.empty()) { q.push(a.top()); a.pop(); } } } } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>in[i]; } for(int i=0;i<n;i++) { cin>>post[i]; } Node* root=create(0,n-1,0,n-1); levelorder(root); for(int i=0;i<n;i++) { if(i!=0) cout<<" "; cout<<s[i]; } system("pause"); return 0; }