二叉樹 已知前序，中序求後序 TOJ 3988

由前序，中序來遞歸的求後序；其實就是按照前序的順序，中序遞歸的分為左中右三部分。再分别遞歸；直到遞歸出口，即為後序字元；

代碼如下；

#include <iostream>
#include <string>
using namespace std;
string pre, in;
/*
 pre_s 目前的前序的起始；pre_e 目前前序的結束；
 in_s 目前的中序的起始， in_e 目前中序的結束
*/
void Post(int pre_s, int pre_e, int in_s, int in_e)
{
	if (in_s > in_e) return;
	if (in_s == in_e) { cout << in[in_s]; return; }
	int k;
	for (k = in_s; k <= in_e; k++)
		if (in[k] == pre[pre_s]) break;
	Post(pre_s + 1, pre_s+k-in_s, in_s, k-1);
	Post(pre_s + k -in_s+1,pre_e,k + 1, in_e);
	cout << pre[pre_s];
}
int main()
{
	while (cin>>pre>>in)
	{
		int len = pre.length();
		Post(0, len - 1, 0, len - 1);
		cout << endl;
	}
}