2345 - 求先序排列
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
Input
每个测试文件只包含一组测试数据，每组输入包含两行，第一行输入一个字符串表示二叉树的中序排列，第二行输入一个字符串表示二叉树的后序排列。
Output
对于每组输入数据，输出二叉树的先序排列。
Examples
Input
BADC BDCA
Output
ABCD
Solution C
#include <stdlib.h> void root( char *mid, char *last ) { char a,*x,*y; if(!*mid) return; x= last+strlen(last)-1; printf("%c",*x); y=strchr(mid,*x); *x=0x0; x=y-mid+last; a=*x; *x=0x0; *y=0x0; root(mid,last); *x=a; root( y+1,x); } int main() { char mid[50]; char last[50]; scanf("%s%*c%s%*c",mid,last); root(mid,last); printf( "\n" ); return 0; }
Solution C++
#include <iostream> #include <string.h> using namespace std; void build(int n,char* s1,char* s2){ if(n<=0) return; int p=strchr(s2,s1[n-1])-s2; cout<<s1[n-1]; build(p,s1,s2); build(n-1-p,s1+p,s2+p+1); } int main() { char s1[100],s2[100]; while(cin>>s2>>s1) { int n=strlen(s1); build(n,s1,s2); cout<<endl; } return 0; }