思路：
递归建树，层序存储，输出
#include <iostream> #include <stdio.h> #include <algorithm> #include <cstring> #include <map> #include <queue> #include <vector> using namespace std; typedef struct tree* treebin; struct tree { treebin left,right; int num,lv; }; vector<int >a[35]; int In[35]; int Post[35]; treebin root = new tree ; treebin Build(int Inst[],int Pst[],int len ) { treebin p=new tree; if(!len) return NULL; int pos=0; for(int i=0;i<len;i++) { if(Pst[len-1]==Inst[i]) { pos=i; break; } } p->num=Inst[pos]; p->right=Build(Inst+pos+1,Pst+pos,len-pos-1); p->left=Build(Inst,Pst,pos); return p; } int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>In[i]; } for(int i=0;i<n;i++) { cin>>Post[i]; } root=Build(In,Post,n ); root->lv=1; queue<treebin>q; q.push(root); int cnt=1,maxx=0; while(!q.empty() ) { treebin ft=q.front(); q.pop(); if(ft->left) { ft->left->lv=ft->lv+1; maxx=max(maxx,ft->lv+1); q.push(ft->left); } if(ft->right) { ft->right->lv=ft->lv+1; maxx=max(maxx,ft->lv+1); q.push(ft->right); } a[ft->lv].push_back(ft->num); } cout<<root->num; for(int i=2;i<=maxx;i++) { if(i&1) { for(int j=a[i].size()-1;j>=0;j--) { cout<<" "<<a[i][j]; } } else { for(int j=0;j<a[i].size();j++) { cout<<" "<<a[i][j]; } } } cout<<endl; }
