d861: NOIP2001 3.求先序排列

解題心得

首先，先搞清楚中序跟後序等表示法。

中序: 左子樹、自己、右子樹；後序: 左子樹、右子樹、自己；前序: 自己、左子樹、右子樹。

因此要找「自己」，也就是前序表示法，要參考中序與後序提供的資訊。

要找到當前字串的「自己」，很明顯就是最右邊的字母。接下來要分別往左右子樹搜尋，則要利用中序字串來切割，遞迴下去。

所以每次都要找當前中序字串位於後序表達式中最右邊的字母，找到以後以它為基準，在中序字串中往左跟往右遞迴搜尋。為了方便計算，提前記錄好字母的位置，用一個大小為26的陣列紀錄所有大寫字母。

因為不存在於輸入的字母不會被存取到，直接擺零即可。

我都是看別人教學才會。

程式碼

#include <iostream>
using namespace std;

string inOrder, postOrder;
int order[26] = { 0 };
void printPreorder(int start, int end)
{
	if (start <= end)
	{
		int flag = -1, val = -1;
		for (int i = start; i <= end; i++)
		{
			if (order[inOrder[i] - 'A'] > val)
			{
				val = order[inOrder[i] - 'A'];
				flag = i;
			}
		}
		cout << inOrder[flag];//<< start << " " << flag << " " << flag + 1 << " " << end << endl;
		printPreorder(start, flag - 1);
		printPreorder(flag + 1, end);
	}
}
int main()
{
	
	cin >> inOrder >> postOrder;
	int start = 0, end = postOrder.length() - 1;
	for (int i = 0; i < postOrder.length(); i++)
		order[postOrder[i] - 'A'] = i;
	printPreorder(start, end);
	return 0;
}