UVa 548 Tree：從中序與後序遍歷重建二叉樹，求最小路徑和葉節點

問題描述

給定二叉樹的中序遍歷和後序遍歷序列（節點值唯一、正整數）。節點權值 = 從根到該節點路徑上所有節點值之和。求權值最小的葉節點值；若多個權值相同，取節點值最小者。

樹的重建

後序最後一個是根。在中序中找到根，左邊為左子樹，右邊為右子樹。遞歸構建：

Node* build(int inL, int inR, int postRootIdx) {
    Node* cur = new Node(post[postRootIdx]);
    if (inL == inR) return cur;
    int i = inL;
    while (in[i] != post[postRootIdx]) i++;
    int leftSize = i - inL;
    if (leftSize > 0)
        cur->left = build(inL, i-1, postRootIdx - 1 - (inR - i));
    if (i < inR)
        cur->right = build(i+1, inR, postRootIdx - 1);
    return cur;
}

DFS 求最小葉節點路徑和

void dfs(Node* u, int sum) {
    sum += u->val;
    if (!u->left && !u->right) { // 葉節點
        if (sum < minSum || (sum == minSum && u->val < ansVal)) {
            minSum = sum; ansVal = u->val;
        }
    }
    if (u->left) dfs(u->left, sum);
    if (u->right) dfs(u->right, sum);
}

完整 C++ 代碼（含輸入解析）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005, INF = 0x3f3f3f3f;
int in[MAXN], post[MAXN];
int minSum = INF, ansVal;

struct Node { int val; Node *l, *r; Node(int v):val(v),l(0),r(0) {} };

Node* build(int il, int ir, int pr) {
    Node* cur = new Node(post[pr]);
    if (il == ir) return cur;
    int i = il;
    while (in[i] != post[pr]) i++;
    int leftSz = i - il;
    if (leftSz > 0) cur->l = build(il, i-1, pr - 1 - (ir - i));
    if (i < ir) cur->r = build(i+1, ir, pr - 1);
    return cur;
}

void dfs(Node* u, int sum) {
    sum += u->val;
    if (!u->l && !u->r) {
        if (sum < minSum || (sum == minSum && u->val < ansVal))
            minSum = sum, ansVal = u->val;
    }
    if (u->l) dfs(u->l, sum);
    if (u->r) dfs(u->r, sum);
}

int main() {
    char line[100000];
    while (fgets(line, sizeof(line), stdin)) {
        int n = 0, x = 0;
        for (char *p = line; *p; p++) {
            if (isdigit(*p)) x = x*10 + *p-'0';
            else if (x) in[++n] = x, x = 0;
        }
        if (x) in[++n] = x;
        fgets(line, sizeof(line), stdin);
        n = x = 0;
        for (char *p = line; *p; p++) {
            if (isdigit(*p)) x = x*10 + *p-'0';
            else if (x) post[++n] = x, x = 0;
        }
        if (x) post[++n] = x;
        Node* root = build(1, n, n);
        minSum = INF; ansVal = 0;
        dfs(root, 0);
        printf("%d\n", ansVal);
    }
    return 0;
}

複雜度與技巧

• 重建樹：\( O(N^2) \) 暴力找根，N≤10000 稍慢，可用哈希表 val→inIndex 優化至 \( O(N) \)。
• DFS：\( O(N) \)。
• 輸入解析：逐字符讀取數字，遇非數字輸出當前數。
• 記憶體：動態分配節點，遞歸深度 ≤ N，必要時改迭代或增棧。

總結

UVa 548 綜合考察 樹重建（中序+後序）、遞歸遍歷、路徑和累加。關鍵在於正確計算遞歸參數中的後序索引偏移，以及處理多組輸入至 EOF。模板化後可快速解決同類「遍歷序列重建樹」問題。