题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1710
通过先序以及中序遍历建树并且输出后序遍历的结果。
代码如下：
#include<bits/stdc++.h> using namespace std; typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; #define pf printf #define mem(a,b) memset(a,b,sizeof(a)) #define prime1 1e9+7 #define prime2 1e9+9 #define pi 3.14159265 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define scand(x) scanf("%llf",&x) #define f(i,a,b) for(int i=a;i<=b;i++) #define scan(a) scanf("%d",&a) #define mp(a,b) make_pair((a),(b)) #define P pair<int,int> #define dbg(args) cout<<#args<<":"<<args<<endl; #define inf 0x7ffffff inline int read(){ int ans=0,w=1; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); return ans*w; } int n,m,t; const int maxn=1e5+10; const ll mod=10000; struct node{ int data; node *l ,*r; node(){} node(int data = 0,node* l=NULL,node* r=NULL):data(data),l(l),r(r){} }; int in[maxn],pre[maxn],post[maxn]; void build(int l,int r,int& cur,node* &root){//分别是用于建树的区间以及当前扫描的根节点， int flag=-1; f(i,l,r){ if(in[i]==pre[cur]){ flag=i; break; } } if(flag==-1)return; root=new node(in[flag]); ++cur;//t指向先序遍历之后的下一个结点，根节点（先序遍历中所有的结点都可以当做是根节点 if(flag>l)build(l,flag-1,cur,root->l);//保证左子树不为空才能构建 if(flag<r)build(flag+1,r,cur,root->r);//保证右子树不为空,构建完左子树之后t指向的是右子树的根节点 } int cnt=0; void postTraverse(node* root){ if(root){ postTraverse(root->l); postTraverse(root->r); post[++cnt]=root->data; } } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); std::ios::sync_with_stdio(false); while(scan(n)!=EOF){ cnt=0; f(i,1,n)pre[i]=read(); f(i,1,n)in[i]=read(); node* root; int cur=1; build(1,n,cur,root); postTraverse(root); f(i,1,n){ if(i==1)pf("%d",post[i]); else pf(" %d",post[i]); } pf(" "); } }