C 語言二叉樹遍歷還原：前序 ABCD 中序 DCBA 推導後序 DCBA

已知

• 前序 (根左右)：A B C D
• 中序 (左根右)：D C B A

推導步驟

1. 前序首元素 **A 為根**。
2. 中序中 A 左側 **D C B** 為左子樹，右側為空 → A 無右子樹。
3. 前序剩余 **B C D** 對應左子樹，首元素 **B 為左子樹根**。
4. 中序左子樹段 **D C B** 中 B 為根，左側 **D C** 為 B 的左子樹，右側空。
5. 前序左子樹段 **C D** 首元素 **C 為根**。
6. 中序 **D C** 中 C 為根，左側 **D** 為 C 的左子樹。
7. 最終樹形：A 左子 B，B 左子 C，C 左子 D (鏈式左傾)。

後序遍歷 (左右根)

D → C → B → A = **DCBA**

圖示

    A
   /
  B
 /
C
/
D

通用算法

void buildPostOrder(char* pre, char* in, int n, char* post) {
    if (n <= 0) return;
    char root = pre[0];
    int k = strchr(in, root) - in; // 中序根位置
    buildPostOrder(pre+1, in, k, post);           // 左
    buildPostOrder(pre+1+k, in+k+1, n-k-1, post+k); // 右
    post[n-1] = root; // 根最後
}