1. 已知中序和后序，求前序

1.1 題目

題目描述：給一棵二叉樹的中序和后序排列，求它的先序排列。

輸入描述：共兩行，均為大寫字母組成的字符串，分別表示一棵二叉樹的中序和后序

輸入：BADC

? ? ? ? ? ?BDCA

輸出：ABCD

1.2 思想

中序排列： B D A?E C F

后續排列：D B E F C A

1. 根據后續遍歷，最后一個元素為這個樹的根

2. 根據中序遍歷，根節點會把整個序列分成兩部分，左邊為左子樹，右邊為右子樹

3. 在左子樹和右子樹中，又可以進行遞歸（處理方法和剛開始一樣）

1.3 模擬實現

#include<iostream>
using namespace std;
string s1,s2;//操作的范圍用l1,r1,l2,r2標記
void dfs(int l1, int r1, int l2, int r2)
{//遞歸結束if (l1 > r1) return;//先序遍歷，先輸出根節點cout << s2[r2];//根據后續遍歷從中序遍歷中找到根節點int q = l1;while (s1[q] != s2[r2]) q++;//對左右子樹遞歸，注意標記的范圍dfs(l1, q - 1, l2, l2 + q - l1 - 1);dfs(q + 1, r1, l2 + q - l1, r2-1);
}int main()
{cin >> s1 >> s2;//先操作最初序列dfs(0, s1.size()-1, 0, s2.size()-1);return 0;
}

2. 已知中序和先序，求后序

2.1 題目

題目描述：給一棵二叉樹的中序和先序排列，求它的后序排列。

輸入描述：共兩行，均為大寫字母組成的字符串，分別表示一棵二叉樹的中序和先序

輸入：ABEDFCHG

? ? ? ? ? CBADEFGH

輸出：AEFDBHGC

2.2 思想

中序排列： ABEDFCHG

先續排列： CBADEFGH

1. 根據先續遍歷，第一個元素為這個樹的根

2. 根據中序遍歷，根節點會把整個序列分成兩部分，左邊為左子樹，右邊為右子樹

3. 在左子樹和右子樹中，又可以進行遞歸（處理方法和剛開始一樣）

2.3 模擬實現

#include<iostream>
using namespace std;
string s1, s2;void dfs(int r1, int l1, int r2, int l2)
{//遞歸結束條件if (r1 > l1) return;//找到中序排列的根節點int p = r1;while (s1[p] != s2[r2]) p++;//遞歸，注意左、右子樹的下標位置dfs(r1, p - 1, r2 + 1, r2 + p - r1 );dfs(p + 1, l1, r2 + p - r1+1, l2);cout << s2[r2];}int main()
{cin >> s1 >> s2;//標記初始序列dfs(0, s1.size() - 1, 0, s2.size()-1);return 0;
}