POJ 2255 Tree Recovery

タイトルのソース:http://poj.org/problem?id=2255
Tree Recovery
Time Limit: 1000 MS
 
メモリLimit: 65536 K
Total Submissions: 11649
 
Acceepted: 7311
Description
Little Valentine liked playing with binary trees very much.Her favorite game was constructing rand mly looking binary trees with capital letters in the nodes. 
This is an example of one of her creations: 

                                               D

                                              / \

                                             /   \

                                            B     E

                                           / \     \

                                          /   \     \

                                         A     C     G

                                                    /

                                                   /

                                                  F

Torecorder trees for future generation s、she wrote down twostins for each tree:a preorder trversal(root、left subtree、rightsubtree)and n inorder trtrtrsal(left subtree、roote、rototrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtre))FFFFFFFtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtreeeeeedededededededededededer 
She thought that such a pair of stregs would give enough information to reconstruct the tree later(but she never tried it) 
Now、years later、looking again the streings、she realized that reconstructining the trees indeed possible、but only because she never had the same letter twice in the same tree. 
However，dong the reconstruction by hand，son turned out to be tedious. 
So now she asks you to write a program that does the job for her！ 
Input
The input will contain one or more test cases. 
Each test case consists of one line containing two streings preord and inord，representing the preorder trversal and inorder trversal of a binary tree.Both stings consist of unique capital letters. 
Input is terminated by end of file. 
Output
For each test case、recover Valentine's binary tree and print one line containing the tree's postorder trversal(left subtree、right subtree、root)
Sample Input

DBACEGF ABCDEFG
BCAD CBAD

Sample Output

ACBFGED
CDAB

ソurce
Ulm Local 1997
件名:
二叉の木の前の順序と中の順序を与えて、後の順序を求めて巡回します。
クイズ:
三つの遍歴の特徴によって
1.前の順序：ルートの左右
2.中順巡回：左 本の右 
3.後順巡回：左右 右側
まず、前の順序に従ってルートノードを巡回して決定し、左のサブツリーと右のサブツリーを中間順に巡回して決定し、その後、この方法で左のサブツリーと右のサブツリーを順次再帰し、ルートノードをスタックに入れる。
最後に、スタックに保存されているのは、この木の後端が巡回されています。
PS：この問題は半年前に見たことがありますが、その時は木の遍歴に慣れていません。まだ完全に理解していないので、コードをかけません。 今日の昼にまたこの問題を訳して、少し分析してすぐに実現しました。一次AC
ACコード:

#include<iostream>
#include<string>
using namespace std;
int posmap[256];
string pretree,midtree,posttree="";
void init()
{
	posttree="";
	for(int i=0;i<pretree.size();i++)
	posmap[pretree[i]]=i+1;
}
void postorder(int left,int right)
{
	if(left==right) return ;
	int Min=posmap[midtree[left]],Mpos=left;
	for(int i=left+1;i<right;i++){
		if(Min>posmap[midtree[i]]){
			Min=posmap[midtree[i]];
			Mpos=i;
		}
	}
	postorder(left,Mpos);
	postorder(Mpos+1,right);
	posttree+=midtree[Mpos];
}
int main()
{
	while(cin>>pretree>>midtree)
	{
		init();
		postorder(0,midtree.size());
		cout<<posttree<<endl;
	}
	return 0;
}