HLG 2040 二叉樹的遍歷 （二叉樹遍歷之間的轉換）

給出一棵二叉樹的中序和前序遍歷，輸出它的後序遍歷。

Input

本題有多組數據，輸入處理到文件結束。

每組數據的第一行包括一個整數n，表示這棵二叉樹一共有n個節點。

接下來的一行每行包括n個整數，表示這棵樹的中序遍歷。

接下來的一行每行包括n個整數，表示這棵樹的前序遍歷。

3<= n <= 100

Output

每組輸出包括一行，表示這棵樹的後序遍歷。

Sample Input

7
4 2 5 1 6 3 7
1 2 4 5 3 6 7

Sample Output

4 5 2 6 7 3 1
 

代碼如下：

#include 
#include 
#include 
#include 
#define MAXN 10005
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int inorder_table[MAXN];
int preorder_table[MAXN];
int position[MAXN], n;

void work( int in_l, int in_r, int pre_l, int pre_r)
{
	int pos;
	if(in_l == in_r) {
		cout << inorder_table[in_l] << ' ';
		return;
	}
	pos = position[preorder_table[pre_l]];
	if(in_l <= ( pos - 1)) work(in_l, pos-1, pre_l+1, pos-in_l+pre_l);
	if((pos + 1) <= in_r) work(pos+1, in_r, pre_r-in_r+pos+1, pre_r);
	cout << inorder_table[pos] << ' ';
}

int main()
{
	while(cin >> n) {
        RST(inorder_table), RST(preorder_table), RST(position);
		for(int i=1; i<=n; i++) {
			cin >> inorder_table[i];
			position[inorder_table[i]] = i;
		}
		for(int i=1; i<=n; i++) cin >> preorder_table[i];
		work(1, n, 1, n);
		cout << endl;
	}
	return 0;
}