POJ2255【题目链接】click here~~
代码：
/** Problem: POJ No.2255 && UVA 536* Running time: 0MS* Complier: G++* Author: javaherongwei* Create Time: 2015-08-18 10:35:06 星期五* binary search tree*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N= 1e2+10;char res[N],pre[N],in[N],last[N];void findlast(int n,char* pre,char* in,char* res)///递归构造,输入先序遍历，，中序遍历，求后序遍历{if(n<=0) return ;int p=strchr(in,pre[0])-in;///找到根节点在中序遍历的位置findlast(p,pre+1,in,res);///递归构造左子树的后序遍历findlast(n-p-1,pre+p+1,in+p+1,res+p);///递归构造右子树的后序遍历res[n-1]=pre[0];///添加根节点到最后面}int main(){while(scanf("%s%s",pre,in)==2){int n=strlen(in);findlast(n,pre,in,res);res[n]='\0';printf("%s\n",res);} return 0;}另一种写法：#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N=100+10;char pre[N],in[N],last[N];void Find_Last(int p1,int p2,int q1,int q2,int root){if(p1>p2) return;for(root=q1; in[root]!=pre[p1]; ++root);Find_Last(p1+1,p1+root-q1,q1,root-1,0);Find_Last(p1+root+1-q1,p2,root+1,q2,0);printf("%c",in[root]);}int main(){while(scanf("%s%s",pre,in)==2){int len=strlen(pre)-1;Find_Last(0,len,0,len,0);puts("");} return 0;}/**输入先序遍历，中序遍历，求后序遍历*样例：DBACEGF ABCDEFGACBFGEDBCAD CBADCDAB*/HDU 1710【题目链接】：click here~~
写法仿照上题。
/** Problem: HDU No.1710* Running time: 62MS* Complier: G++* Author: javaherongwei* Create Time: 2015-09-16 14:37:06 星期三* binary search tree*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int N=1e4+10;int pre[N],in[N],last[N];void Find_Last(int p1,int p2,int q1,int q2,int root,int ck) // 标记一个变量{if(p1>p2) return;for(root=q1; in[root]!=pre[p1]; ++root);Find_Last(p1+1,p1+root-q1,q1,root-1,0,0);Find_Last(p1+root+1-q1,p2,root+1,q2,0,0);if(ck==1) printf("%d",in[root]);else printf("%d ",in[root]);}int main(){int t;while(~scanf("%d",&t)){for(int i=0; i<t; ++i) scanf("%d",&pre[i]);for(int i=0; i<t; ++i) scanf("%d",&in[i]);Find_Last(0,t-1,0,t-1,0,1);puts("");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
会让你的心态更平和更坦然，也会让你心无旁骛，更会让你的心灵得到解脱和抚慰。
