POJ 2255 Tree Recovery

想法：
　　原本的字串是整棵Tree，我們可先找到這個Tree的Root，再將其分為左右Sub Tree，一直遞迴下去直到Sub Tree只剩一個元素。
　　具體做法是：

1. 先用Preorder String找出Root(P_root)，再透過P_root找到Inorder String的Root(I_root)
2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index：左子樹的左右界和右子樹的左右界)，再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
3. 依照Post Order的順序：
1. 先遞迴左子樹
2. 再遞迴右子樹
3. 輸出Root

底下有附詳細註解的Code：

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char Preorder[30], Inorder[30];
	void Postorder(int PL, int PR, int IL, int IR);
	int FindInorderRoot(char c, int L, int R);
	int main()
	{
	while (scanf("%s %s", Preorder, Inorder) == 2) {
	Postorder(0, strlen(Preorder)-1, 0, strlen(Inorder)-1);
	putchar('\n');
	}
	return 0;
	}
	void Postorder(int PL, int PR, int IL, int IR) // PL, PR: Preorder的左右界 IL, IR: Inorder的左右界
	{
	if (PL == PR) { // 左界等於右界,
	printf("%c", Preorder[PL]);
	return;
	}
	// P_root, I_root: 目前這個Tree的root的index
	int P_root = PL;
	int I_root = FindInorderRoot(Preorder[P_root], IL, IR);
	// 要分成左右子樹, P_Lsub_L, P_Lsub_R: 為左子樹在Preorder的左右界,反之另外兩個為右子樹左右界
	int P_Lsub_L, P_Lsub_R, P_Rsub_L, P_Rsub_R;
	// I_Lsub_L, I_Lsub_R: 為左子樹在Inorder的左右界,另外兩個為右子樹的左右界
	int I_Lsub_L, I_Lsub_R, I_Rsub_L, I_Rsub_R;
	bool hasLsub = 1, hasRsub = 1; //確認左右子樹是否存在
	I_Lsub_L = IL;
	I_Lsub_R = I_root - 1;
	if (I_Lsub_L > I_Lsub_R) hasLsub = 0;
	I_Rsub_L = I_root + 1;
	I_Rsub_R = IR;
	if (I_Rsub_L > I_Rsub_R) hasRsub = 0;
	if (hasLsub) {
	P_Lsub_L = P_root + 1;
	P_Lsub_R = P_Lsub_L + (I_Lsub_R - I_Lsub_L);
	}
	if (hasRsub) {
	P_Rsub_L = (hasLsub) ? P_Lsub_R + 1 : P_root + 1;
	P_Rsub_R = PR;
	}
	//若左(右)子樹存在,則繼續遞迴分割,直到元素剩下一個
	//底下三行code的順序為Postorder(Left, Right, Root)
	if (hasLsub) Postorder(P_Lsub_L, P_Lsub_R, I_Lsub_L, I_Lsub_R);
	if (hasRsub) Postorder(P_Rsub_L, P_Rsub_R, I_Rsub_L, I_Rsub_R);
	printf("%c", Preorder[P_root]);
	}
	int FindInorderRoot(char c, int L, int R)
	{
	while (Inorder[L] != c && L <= R) L++;
	return L;
	}

view raw [POJ] 2255 Tree Recovery.cpp hosted with ❤ by GitHub