【POJ - 2255】Tree Recovery （给定树的先序中序，输出后序）

题干：

Input

The input will contain one or more test cases. 
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.) 
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 traversal (left subtree, right subtree, root).

Sample Input

DBACEGF ABCDEFG
BCAD CBAD

Sample Output

ACBFGED
CDAB

题目大意：

给定一棵树的先序中序，让你输出后序遍历的序列。

解题报告：

直接模拟

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
struct Node {
	char val;
	int l,r;
} p[MAX];
int tot;
char q[MAX],z[MAX],h[MAX];
int dfs(char q[],char z[],int len) {
	if(len == 0) return -1;
	int cur = ++tot;
	p[cur].val = q[1];
	p[cur].l = p[cur].r = -1;
	if(len == 1) return cur;
	int tar = 0;
	for(int i = 1; i<=len; i++) {
		if(z[i] == q[1]) {
			tar = i;break;
		}
	}	
	p[cur].l = dfs(q+1,z,tar-1);
	p[cur].r = dfs(q+tar,z+tar,len-tar);
	return cur;
}
void out(int cur) {
	if(p[cur].l != -1) out(p[cur].l);
	if(p[cur].r != -1) out(p[cur].r);
	printf("%c",p[cur].val); 
}
int main()
{
	while(~scanf("%s%s",q+1,z+1)) {
		tot=0;
		int len = strlen(q+1);
		dfs(q,z,len);
		out(1);
		puts("");
	} 
	return 0 ;
}