3.4.2 American Heritage 美国血统

3.4.2 American Heritage 美国血统

时间： 1ms        内存：64M

描述：

农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性 的”树的中序遍历“和”树的前序遍历“的符号加以记录而不是用图形的方法。 你的任务是在被给予奶牛家谱的”树中序遍历“和”树前序遍历“的符号后，创建奶牛家谱的”树的后序遍历“的符号。每一头奶牛的姓名被 译为一个唯一的字母。（你可能已经知道你可以在知道树的两种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多余26个的顶点。 这是在样例输入和样例输出中的树的图形表达方式：

                  C
                /   \
               /     \
              B       G
             / \     /
            A   D   H
               / \
              E   F

树的中序遍历是打印左子树，根和右子树。 树的前序遍历是打印根，左子树和右子树。 树的后序遍历是打印左子树，右子树和根。

输入：

第一行： 树的中序遍历 第二行： 同样的树的前序遍历

输出：

单独的一行表示该树的后序遍历。

示例输入：

ABEDFCHG
CBADEFGH

示例输出：

AEFDBHGC

提示：

参考答案（内存最优[748]）：

#include <stdio.h>
#include <string.h>
char a[30],b[30];
int len,cnt;
void solve(int s,int e){
	int i;
	if(s==e || cnt==len)
		return ;
	/*if(s==e-1){
		printf("%c",a[s]);
		return ;
	}*/
	for(i=s;i<e;i++){
		if(a[i]==b[cnt])
			break;
	}
	if(s<i){
		cnt++;
		solve(s,i);
	}
	if(i<e-1){
		cnt++;
		solve(i+1,e);
	}
	printf("%c",a[i]);
}

int main(){
	while(scanf("%s%s",a,b)!=EOF){
		len=strlen(a);
		cnt=0;
		solve(0,len);
		printf("\n");
	}
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h>
char a[1000];
char b[1000];
int n;
int search(int x1,int y1,int x2,int y2)
{
	if(x1>y1)
	{
		return 0; 
	}
	else if(x1==y1)
	{
		printf("%c",a[x1]);
		return 0;
	}
	else
	{
		int mid;
		for(int i=x2;i<=y2;i++)//寻找分割点
		{
			if(b[i]==a[x1])
			mid=i;
		}
		search(x1+1,x1+mid-x2,x2,mid-1);
		search(x1+mid-x2+1,y1,mid+1,y2);
		printf("%c",a[x1]);//a[x1]表示首节点 
	}
}
int main()
{
	gets(b);
	gets(a);
	n=strlen(a);
	search(0,n-1,0,n-1);
} 

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。