二叉樹三種遍歷統一輸入輸出格式解題：遞歸模板套用技巧

題目規範

輸入：節點數 n，隨後 n 行每行兩整數 L R 表示第 i 個節點的左右孩子編號（0 為空）。
輸出：三行，分別為前序、中序、後序遍歷序列，編號用空格分隔。

遞歸模板法

利用兩個陣列 L[i], R[i] 存儲左右孩子。三個遍歷函數僅打印位置不同：

void pre(int u) {      // 前序：根左右
    printf("%d ", u);
    if (L[u]) pre(L[u]);
    if (R[u]) pre(R[u]);
}
void in(int u) {       // 中序：左根右
    if (L[u]) in(L[u]);
    printf("%d ", u);
    if (R[u]) in(R[u]);
}
void post(int u) {     // 後序：左右根
    if (L[u]) post(L[u]);
    if (R[u]) post(R[u]);
    printf("%d ", u);
}

完整 AC 代碼

#include <stdio.h>
int L[101], R[101];

void pre(int u) { printf("%d ", u); if(L[u]) pre(L[u]); if(R[u]) pre(R[u]); }
void in(int u)  { if(L[u]) in(L[u]); printf("%d ", u); if(R[u]) in(R[u]); }
void post(int u){ if(L[u]) post(L[u]); if(R[u]) post(R[u]); printf("%d ", u); }

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &L[i], &R[i]);
    pre(1); printf("\n");
    in(1);  printf("\n");
    post(1); printf("\n");
    return 0;
}

樣例驗證

輸入：
5
2 3
4 5
0 0
0 0
0 0

輸出：
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

核心技巧總結

1. 陣列下標即節點編號，無需指針結構體。
2. 三遍遞歸代碼高度相似，複製修改打印順序即可，極低出錯率。
3. 根節點固定為 1，遞歸自然終止於 0。