數據結構經典題：已知中序與層次遍歷序列重構二叉樹

題目

二叉樹 T 的中序遍歷：`B A F D G C E`
層次遍歷：`A B C D E F G`
畫出該二叉樹。

重構邏輯步驟

1. 層次遍歷第一個節點是根 → **A 是根節點**。
2. 在中序中找到根 A → 左側 `B` 為左子樹，右側 `F D G C E` 為右子樹。
3. 看層次遍歷中根之後的節點：`B C D E F G`。
   - `B` 在中序左側 → **B 是 A 的左孩子**（左子樹僅有 B）。
   - `C` 在中序右側 → **C 是 A 的右孩子**（右子樹根）。
4. 遞歸處理右子樹（根 C，中序 F D G C E）：
   層次剩餘 `D E F G`。
   - `D` 在中序 C 左側 (`F D G`) → **D 是 C 的左孩子**。
   - `E` 在中序 C 右側 (`E`) → **E 是 C 的右孩子**。
5. 遞歸處理 D 的子樹（中序 F D G）：
   層次剩餘 `F G`。
   - `F` 在 D 左側 → **F 是 D 的左孩子**。
   - `G` 在 D 右側 → **G 是 D 的右孩子**。

最終樹結構

        A
       / \
      B   C
         / \
        D   E
       / \
      F   G

驗證

• 中序：B (左) → A (根) → F (左) → D (根) → G (右) → C (根) → E (右) ✅
• 層次：A → B C → D E → F G ✅

通用算法模板

TreeNode* buildTree(vector& level, vector& in) {
    if (level.empty()) return nullptr;
    int rootVal = level[0];
    TreeNode* root = new TreeNode(rootVal);
    auto it = find(in.begin(), in.end(), rootVal);
    vector inLeft(in.begin(), it);
    vector inRight(it + 1, in.end());
    
    // 從 level[1:] 中按 inLeft/inRight 篩選出左右子樹的層次序列
    vector levelLeft, levelRight;
    for (int i = 1; i < level.size(); ++i) {
        if (binary_search(inLeft.begin(), inLeft.end(), level[i])) // 需排序或用 unordered_set
            levelLeft.push_back(level[i]);
        else
            levelRight.push_back(level[i]);
    }
    root->left = buildTree(levelLeft, inLeft);
    root->right = buildTree(levelRight, inRight);
    return root;
}

**核心洞見：層次遍歷給根與「橫向順序」，中序遍歷給「縱向劃分」，兩者結合即可唯一確定樹。**