1. 原題： https://www.patest.cn/contests/pat-a-PRactise/1086

2. 思路：

3. 源碼：

#include<iostream>#include<vector>#include<stack>#include<string>using namespace std;int N;//結點數vector<int> ino, pre;//分別存儲中序和前序的序列int findPos(int x);//找出前序中的第x個元素在中序的位置void post(int left, int right, int ro_pos);//輸出后序, 參數分別是中序的左、右邊界，前序的根位置int main(void){	//freopen("in.txt", "r", stdin);	cin >> N;	stack<int> sta;//棧	for (int i = 0; i < 2 * N; i++)//讀入數據	{		string s;		int data;		cin >> s;		if (s[1] == 'u')//構建前序序列		{			cin >> data;			sta.push(data);			pre.push_back(data);		}		else//構建中序序列		{			data = sta.top();			sta.pop();			ino.push_back(data);		}	}	post(0, N - 1, 0);//遞歸輸出后序	return 0;}int findPos(int x)//找出前序中的第x個元素在中序的位置{	int i;	for (i = 0; i < N; i++)	{		if (ino[i] == pre[x])			break;	}	return i;}void post(int left, int right, int ro_pos)//參數分別是中序的左、右邊界，前序的根位置{	if (left > right)//遞歸終止條件		return;	int ino_pos = findPos(ro_pos);	post(left, ino_pos - 1, ro_pos + 1);//遞歸左子樹	post(ino_pos + 1, right, (ro_pos + ino_pos - left + 1));//遞歸右子樹	if (ro_pos == 0)//輸出根結點		cout << pre[ro_pos] << endl;	else		cout << pre[ro_pos] << ' ';}