usaco 3.4.2

Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear `tree in-order' and `tree pre-order' notations.

Your job is to create the `tree post-order' notation of a cow's heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.

Here is a graphical representation of the tree used in the sample input and output:

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

The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.

The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.

The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.

PROGRAM NAME: heritage

INPUT FORMAT

SAMPLE INPUT (file heritage.in)

ABEDFCHG
CBADEFGH

OUTPUT FORMAT

SAMPLE OUTPUT (file heritage.out)

AEFDBHGC 

一道很简单的题，已知二叉树的中序遍历和先序遍历，求后序遍历。对二叉树的遍历，和递归有点认识的话，没压力。。。

/*
ID: fwj_ona1
LANG: C++
TASK: heritage
*/

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;

char M[27],F[27],L[27];

void run(int b,int e,int root);
int main ()
{
	freopen ("heritage.in","r",stdin);
    freopen ("heritage.out","w",stdout);
	scanf("%s",M);
	scanf("%s",F);
	run(0,strlen(M)-1,0);
	printf("\n");
	return 0;
}

void run(int b,int e,int root)
{
	if(b>e)
		return;
	if(b==e)
	{
		printf("%c",F[root]);
		return;
	}
	int set;
	for(int i=b;i<=e;i++)
		if(M[i]==F[root])
		{
			set=i;
			break;
		}
	run(b,set-1,root+1);
	run(set+1,e,root+set-b+1);
	printf("%c",F[root]);
}