PAT 甲級 1030 Tree Traversals Again：堆疊序列重建二叉樹並輸出後序遍歷

編輯：關於C語言

題目大意

給定一棵 N 節點（1~N 編號）二叉樹的中序遍歷過程中堆疊操作序列（Push X / Pop），該序列唯一確定一棵二叉樹。要求輸出該樹的後序遍歷序列。

範例：

輸入：
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

輸出：
3 4 2 6 5 1

核心洞察：堆疊操作即「先序+中序」編碼

Push X：訪問節點 X → 屬於先序遍歷順序
Pop：彈出節點 → 屬於中序遍歷順序

因此，輸入的 2N 行操作直接給出了先序序列與中序序列。經典問題：已知先序與中序，求後序。

演算法步驟

模擬堆疊，提取先序序列 pre[] 與中序序列 in[]
遞歸構建後序序列 post[]：
- 先序首元素為根節點
- 在中序中定位根節點，左側為左子樹，右側為右子樹
- 遞歸處理左右子樹，最後將根節點放入後序數組尾部
輸出 post[]

關鍵代碼實現（C 語言）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { int *a; int top; } SeqStack;

void push(SeqStack *s, int x) { s->a[++(s->top)] = x; }
int pop(SeqStack *s) { return s->a[s->top--]; }

// 遞歸構建後序：preL/inL/postL 為當前子樹在三個數組中的起始索引，n 為節點數
void solve(int *pre, int *in, int *post, int preL, int inL, int postL, int n) {
    if (n == 0) return;
    if (n == 1) { post[postL] = pre[preL]; return; }

    int root = pre[preL];
    post[postL + n - 1] = root;  // 根節點放在後序區間末尾

    int i, L = 0;
    for (i = 0; i < n; i++) if (in[inL + i] == root) { L = i; break; }
    int R = n - L - 1;

    solve(pre, in, post, preL + 1,     inL,         postL,     L);       // 左子樹
    solve(pre, in, post, preL + L + 1, inL + L + 1, postL + L, R);       // 右子樹
}

int main() {
    int N; scanf("%d", &N);
    SeqStack S; S.a = malloc(N * sizeof(int)); S.top = -1;
    int pre[N], in[N], post[N];
    int pre_idx = 0, in_idx = 0;

    for (int i = 0; i < 2 * N; i++) {
        char op[5]; int x;
        scanf("%s", op);
        if (strcmp(op, "Push") == 0) {
            scanf("%d", &x);
            pre[pre_idx++] = x;
            push(&S, x);
        } else { // Pop
            in[in_idx++] = pop(&S);
        }
    }

    solve(pre, in, post, 0, 0, 0, N);
    for (int i = 0; i < N; i++) {
        printf("%d%c", post[i], i == N-1 ? '\n' : ' ');
    }
    free(S.a);
    return 0;
}