從中序與後序遍歷重構二叉樹前序遍歷：遞歸分治 O(n) 解法

問題描述

給定二叉樹的中序遍歷序列 Inorder 與後序遍歷序列 Postorder（節點用大寫字母表示，長度 ≤ 8），求前序遍歷序列 Preorder。

範例：
Inorder: B A D C
Postorder: B D C A
Preorder: A B C D

核心性質

• 後序最後一個元素 = 根節點。
• 中序中根節點左側 = 左子樹，右側 = 右子樹。
• 左右子樹在後序中連續分布，長度與中序對應段相等。

遞歸分治算法

1. 取後序最後一字符 root = post[post_len-1]，輸出（前序首）。
2. 在中序中定位 root 下標 idx。
3. 左子樹規模 = idx，右子樹規模 = in_len - idx - 1。
4. 遞歸處理左子樹：
     in[0..idx-1], post[0..idx-1]
5. 遞歸處理右子樹：
     in[idx+1..end], post[idx..post_len-2]

Java 參考實現

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String in = sc.nextLine().trim();
            String post = sc.nextLine().trim();
            showResult(in, post);
            System.out.println();
        }
    }

    static void showResult(String in, String post) {
        if (in.isEmpty()) return;
        char root = post.charAt(post.length() - 1);
        System.out.print(root);
        int idx = in.indexOf(root);
        if (idx > 0)
            showResult(in.substring(0, idx), post.substring(0, idx));
        if (idx < in.length() - 1)
            showResult(in.substring(idx + 1), post.substring(idx, post.length() - 1));
    }
}

複雜度分析

• 時間：O(n²) —— 每層 indexOf 掃描 O(n)，共 n 層。
  若預處理字符→下標映射表，可降至 O(n)。
• 空間：O(n²) 字符串切片開銷（Java substring 共享底層 char[] 故實際 O(n)）；遞歸棧 O(n)。

關鍵細節

• 輸入可能包含多組測試用例，需循環讀取直到 EOF。
• 空樹情況：in.isEmpty() 直接返回。
• 右子樹後序切片起始下標為 idx（跳過左子樹 idx 個元素），結尾排除根節點。

延伸：若需構建實際樹結構

同理遞歸，返回 TreeNode 而非直接打印。LeetCode 106「從中序與後序遍歷構造二叉樹」即為此變體。