#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 50		// 每棵樹的最大 node 數

// 函式說明：將 PreOrder 與 InOrder 轉成 PostOrder
// 參數 ppcPreOrder：PreOrder 正要被處理的 node 之 pointer to pointer
// 參數 pcInOrderLowerBound：要處理的分支在 InOrder 中的 Lower Bound 位址
// 參數 pcInOrderUpperBound：要處理的分支在 InOrder 中的 Upper Bound 位址
// 參數 ppcPostOrder：PostOrder 要插入的 node 之 pointer to pointer
void Translate(char **ppcPreOrder, 
			   char *pcInOrderLowerBound, char *pcInOrderUpperBound, 
			   char **ppcPostOrder)
{
	char cPreOrder;							// PreOrder 正要被處理的 node
	char *pcInOrder = pcInOrderLowerBound;	// cPreOrder 在 InOrder 中之位址

	// 如果要處理的 LowerBound 等於 UpperBound，表示這個分支已處理完，直接 return
	if(pcInOrderLowerBound == pcInOrderUpperBound)
		return;

	// 取得 PreOrder 正要被處理的 node
	cPreOrder = *(*ppcPreOrder)++;

	// 尋找 PreOrder 要處理的 node 在 InOrder 中的位址
	while(*pcInOrder != cPreOrder)
		++pcInOrder;

	// 處理這個 node 的左邊分支
	Translate(ppcPreOrder, pcInOrderLowerBound, pcInOrder, ppcPostOrder);

	// 處理這個 node 的右邊分支
	Translate(ppcPreOrder, pcInOrder + 1, pcInOrderUpperBound, ppcPostOrder);

	// 把這個 node 加到 PostOrder 中
	*(*ppcPostOrder)++ = cPreOrder;
}

int main()
{
	FILE *fpIn, *fpOut;					// 檔案指標
	int iNumOfNodes;					// 總共有幾個 node
	char *pcPreOrder;					// PreOrder 正要被處理的 node 之位址
	char *pcPostOrder;					// PostOrder 正要插入的 node 之位址
	char szPreOrder[MAX_SIZE];			// PreOrder
	char szInOrder[MAX_SIZE];			// InOrder
	char szPostOrder[MAX_SIZE] = {0};	// PostOrder

	// 讀取 input 檔
	fpIn = fopen("Input.txt", "r");
	fscanf(fpIn, "%d%s%s", &iNumOfNodes, szPreOrder, szInOrder);
	fclose(fpIn);

	// 開始轉換
	pcPreOrder = szPreOrder;
	pcPostOrder = szPostOrder;
	Translate(&pcPreOrder, szInOrder, szInOrder + iNumOfNodes, &pcPostOrder);

	// 寫入 output 檔
	fpOut = fopen("Output.txt", "w");
	fprintf(fpOut, "%s", szPostOrder);
	fclose(fpOut);
	return 0;
}