习题6-3 二叉树重建（Tree Recovery，ULM 1997，UVa 536）

原题链接：https://vjudge.net/problem/UVA-536
分类：树
备注：水题

代码如下：

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string PreOrder, InOrder;
void dfs(int L1, int R1, int L2, int R2)
{
	if (L1 > R1 || L2 > R2)return;
	char root = PreOrder[L1];
	int pos;
	for (pos = L2; InOrder[pos] != root; pos++);
	dfs(L1 + 1, L1 + pos - L2, L2, pos - 1);
	dfs(L1 + pos - L2 + 1, R1, pos + 1, R2);
	printf("%c", root);
}
int main(void)
{
	while (cin >> PreOrder >> InOrder)
	{
		dfs(0, PreOrder.length() - 1, 0, InOrder.length() - 1);
		printf("\n");
	}
	return 0;
}