tree_construct_from_traversals.cpp

/*
 * ============================================================================
 *  由遍歷結果建構二元樹 — Preorder+Inorder / Inorder+Postorder
 *  File: tree_construct_from_traversals.cpp
 *
 *  核心原理:
 *    - Preorder 第一個元素 = root；Postorder 最後一個元素 = root
 *    - 在 Inorder 中找到 root → 左邊 = 左子樹, 右邊 = 右子樹
 *    - 用 HashMap 預處理 Inorder，使查找 root 位置 O(1) → 整體 O(N)
 *
 *  涵蓋:
 *    1. Preorder + Inorder → 建構唯一二元樹
 *    2. Inorder + Postorder → 建構唯一二元樹
 *    3. 驗證: 建構後再做遍歷，確認和輸入一致
 *    4. 視覺化輸出
 *    5. 說明為什麼 Preorder + Postorder 不能唯一確定
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_construct_from_traversals tree_construct_from_traversals.cpp
 * ============================================================================
 */

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <queue>

using namespace std;

/* ============================================================================
 *  節點結構
 * ============================================================================ */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

/* ============================================================================
 *  1. Preorder + Inorder → 建構二元樹
 *
 *  原理:
 *    Preorder: [Root, <左子樹的 Preorder>, <右子樹的 Preorder>]
 *    Inorder:  [<左子樹的 Inorder>, Root, <右子樹的 Inorder>]
 *
 *  步驟:
 *    1. pre[preL] = root
 *    2. 在 inorder 中找到 root 的位置 rootIdx (用 HashMap → O(1))
 *    3. leftSize = rootIdx - inL
 *    4. 遞迴建構左子樹: pre[preL+1 .. preL+leftSize], in[inL .. rootIdx-1]
 *    5. 遞迴建構右子樹: pre[preL+leftSize+1 .. preR], in[rootIdx+1 .. inR]
 *
 *  時間: O(N)  (HashMap 查找 O(1))
 *  空間: O(N)  (HashMap + 遞迴 stack)
 * ============================================================================ */
TreeNode* buildFromPreIn(const vector<int>& preorder, int preL, int preR,
                         const vector<int>& inorder,  int inL,  int inR,
                         unordered_map<int, int>& inMap) {
    // Base case: 區間為空
    if (preL > preR) return nullptr;

    // Step 1: Preorder 的第一個元素是當前子樹的 root
    int rootVal = preorder[preL];
    TreeNode* root = new TreeNode(rootVal);

    // Step 2: 用 HashMap 找 root 在 Inorder 中的位置 — O(1)
    int rootIdx = inMap[rootVal];

    // Step 3: 左子樹的節點數
    int leftSize = rootIdx - inL;

    // Step 4: 遞迴建構左子樹
    // Preorder 中左子樹佔: [preL+1, preL+leftSize]
    // Inorder  中左子樹佔: [inL, rootIdx-1]
    root->left = buildFromPreIn(preorder, preL + 1, preL + leftSize,
                                inorder,  inL,      rootIdx - 1,
                                inMap);

    // Step 5: 遞迴建構右子樹
    // Preorder 中右子樹佔: [preL+leftSize+1, preR]
    // Inorder  中右子樹佔: [rootIdx+1, inR]
    root->right = buildFromPreIn(preorder, preL + leftSize + 1, preR,
                                 inorder,  rootIdx + 1,         inR,
                                 inMap);

    return root;
}

// 驅動函式
TreeNode* buildFromPreorderInorder(const vector<int>& preorder,
                                    const vector<int>& inorder) {
    int n = (int)preorder.size();
    if (n == 0) return nullptr;

    // 預處理: 建立 Inorder 值 → 索引的 HashMap
    unordered_map<int, int> inMap;
    for (int i = 0; i < n; ++i) {
        inMap[inorder[i]] = i;
    }

    return buildFromPreIn(preorder, 0, n - 1, inorder, 0, n - 1, inMap);
}

/* ============================================================================
 *  2. Inorder + Postorder → 建構二元樹
 *
 *  原理:
 *    Postorder: [<左子樹的 Postorder>, <右子樹的 Postorder>, Root]
 *    Inorder:   [<左子樹的 Inorder>, Root, <右子樹的 Inorder>]
 *
 *  步驟:
 *    1. post[postR] = root (Postorder 的最後一個元素)
 *    2. 在 inorder 中找到 root 的位置 rootIdx
 *    3. rightSize = inR - rootIdx
 *    4. 遞迴建構右子樹: post[postR-rightSize .. postR-1], in[rootIdx+1 .. inR]
 *    5. 遞迴建構左子樹: post[postL .. postR-rightSize-1], in[inL .. rootIdx-1]
 *
 *  時間: O(N)
 * ============================================================================ */
TreeNode* buildFromInPost(const vector<int>& inorder,   int inL,   int inR,
                          const vector<int>& postorder, int postL, int postR,
                          unordered_map<int, int>& inMap) {
    // Base case
    if (postL > postR) return nullptr;

    // Step 1: Postorder 的最後一個元素是 root
    int rootVal = postorder[postR];
    TreeNode* root = new TreeNode(rootVal);

    // Step 2: 找 root 在 Inorder 中的位置
    int rootIdx = inMap[rootVal];

    // Step 3: 右子樹的節點數
    int rightSize = inR - rootIdx;

    // Step 4: 遞迴建構右子樹
    // Postorder 中右子樹佔: [postR-rightSize, postR-1]
    // Inorder   中右子樹佔: [rootIdx+1, inR]
    root->right = buildFromInPost(inorder,   rootIdx + 1,         inR,
                                  postorder, postR - rightSize, postR - 1,
                                  inMap);

    // Step 5: 遞迴建構左子樹
    // Postorder 中左子樹佔: [postL, postR-rightSize-1]
    // Inorder   中左子樹佔: [inL, rootIdx-1]
    root->left = buildFromInPost(inorder,   inL,                    rootIdx - 1,
                                 postorder, postL, postR - rightSize - 1,
                                 inMap);

    return root;
}

// 驅動函式
TreeNode* buildFromInorderPostorder(const vector<int>& inorder,
                                     const vector<int>& postorder) {
    int n = (int)inorder.size();
    if (n == 0) return nullptr;

    unordered_map<int, int> inMap;
    for (int i = 0; i < n; ++i) {
        inMap[inorder[i]] = i;
    }

    return buildFromInPost(inorder, 0, n - 1, postorder, 0, n - 1, inMap);
}

/* ============================================================================
 *  遍歷函式（用來驗證建構結果）
 * ============================================================================ */

void getPreorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);
    getPreorder(node->left, result);
    getPreorder(node->right, result);
}

void getInorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    getInorder(node->left, result);
    result.push_back(node->val);
    getInorder(node->right, result);
}

void getPostorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    getPostorder(node->left, result);
    getPostorder(node->right, result);
    result.push_back(node->val);
}

void getLevelOrder(TreeNode* root, vector<int>& result) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        result.push_back(cur->val);
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

/* ============================================================================
 *  視覺化輸出
 * ============================================================================ */
void printTree(TreeNode* node, const string& prefix = "", bool isLeft = true) {
    if (!node) return;

    if (node->right) {
        printTree(node->right, prefix + (isLeft ? "│   " : "    "), false);
    }

    cout << prefix;
    cout << (isLeft ? "└── " : "┌── ");
    cout << node->val << endl;

    if (node->left) {
        printTree(node->left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

/* ============================================================================
 *  輔助: 印出 vector
 * ============================================================================ */
void printVec(const string& label, const vector<int>& v) {
    cout << label;
    for (size_t i = 0; i < v.size(); ++i) {
        if (i > 0) cout << " ";
        cout << v[i];
    }
    cout << endl;
}

/* ============================================================================
 *  釋放記憶體
 * ============================================================================ */
void deleteTree(TreeNode* node) {
    if (!node) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

/* ============================================================================
 *  主程式
 * ============================================================================ */
int main() {
    cout << "============================================================" << endl;
    cout << "  Construct Binary Tree from Traversals" << endl;
    cout << "============================================================\n" << endl;

    /*
     * 目標樹:
     *          1
     *        /   \
     *       2     3
     *      / \   / \
     *     4   5 6   7
     */

    // ─────────────────────────────────────────────
    // 測試 1: Preorder + Inorder
    // ─────────────────────────────────────────────
    cout << "【1. Preorder + Inorder → Build Tree】\n" << endl;

    vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
    vector<int> inorder  = {4, 2, 5, 1, 6, 3, 7};

    printVec("  Input Preorder: ", preorder);
    printVec("  Input Inorder:  ", inorder);
    cout << endl;

    TreeNode* tree1 = buildFromPreorderInorder(preorder, inorder);

    cout << "  Built tree:" << endl;
    printTree(tree1);
    cout << endl;

    // 驗證: 重新做遍歷看是否一致
    vector<int> verify_pre, verify_in, verify_post, verify_level;
    getPreorder(tree1, verify_pre);
    getInorder(tree1, verify_in);
    getPostorder(tree1, verify_post);
    getLevelOrder(tree1, verify_level);

    printVec("  Verify Preorder:    ", verify_pre);
    printVec("  Verify Inorder:     ", verify_in);
    printVec("  Verify Postorder:   ", verify_post);
    printVec("  Verify Level-order: ", verify_level);

    cout << "  Preorder match: " << (verify_pre == preorder ? "YES" : "NO") << endl;
    cout << "  Inorder match:  " << (verify_in  == inorder  ? "YES" : "NO") << endl;
    cout << endl;

    // ─────────────────────────────────────────────
    // 測試 2: Inorder + Postorder
    // ─────────────────────────────────────────────
    cout << "【2. Inorder + Postorder → Build Tree】\n" << endl;

    vector<int> postorder = {4, 5, 2, 6, 7, 3, 1};

    printVec("  Input Inorder:   ", inorder);
    printVec("  Input Postorder: ", postorder);
    cout << endl;

    TreeNode* tree2 = buildFromInorderPostorder(inorder, postorder);

    cout << "  Built tree:" << endl;
    printTree(tree2);
    cout << endl;

    // 驗證
    vector<int> v2_in, v2_post;
    getInorder(tree2, v2_in);
    getPostorder(tree2, v2_post);
    printVec("  Verify Inorder:   ", v2_in);
    printVec("  Verify Postorder: ", v2_post);
    cout << "  Inorder match:   " << (v2_in   == inorder   ? "YES" : "NO") << endl;
    cout << "  Postorder match: " << (v2_post == postorder ? "YES" : "NO") << endl;
    cout << endl;

    // ─────────────────────────────────────────────
    // 測試 3: 較大的樹
    // ─────────────────────────────────────────────
    cout << "【3. Larger Tree Test】\n" << endl;

    /*
     *              50
     *            /    \
     *          30      70
     *         /  \    /  \
     *       20   40  60   80
     *      /       \
     *    10        45
     */
    vector<int> pre3 = {50, 30, 20, 10, 40, 45, 70, 60, 80};
    vector<int> in3  = {10, 20, 30, 40, 45, 50, 60, 70, 80};

    printVec("  Preorder: ", pre3);
    printVec("  Inorder:  ", in3);

    TreeNode* tree3 = buildFromPreorderInorder(pre3, in3);
    cout << "\n  Built tree:" << endl;
    printTree(tree3);

    vector<int> v3_post;
    getPostorder(tree3, v3_post);
    printVec("\n  Derived Postorder: ", v3_post);

    // 用 Inorder + Postorder 重建，驗證一致
    TreeNode* tree3b = buildFromInorderPostorder(in3, v3_post);
    vector<int> v3b_pre;
    getPreorder(tree3b, v3b_pre);
    cout << "  Rebuild from In+Post → Preorder match: "
         << (v3b_pre == pre3 ? "YES" : "NO") << endl;
    cout << endl;

    // ─────────────────────────────────────────────
    // 測試 4: 只有左子樹（歪斜樹）
    // ─────────────────────────────────────────────
    cout << "【4. Skewed Tree (left-only)】\n" << endl;

    vector<int> pre4 = {1, 2, 3, 4};
    vector<int> in4  = {4, 3, 2, 1};

    TreeNode* tree4 = buildFromPreorderInorder(pre4, in4);
    cout << "  Built tree:" << endl;
    printTree(tree4);
    cout << endl;

    // ─────────────────────────────────────────────
    // 測試 5: 單節點
    // ─────────────────────────────────────────────
    cout << "【5. Single Node】\n" << endl;

    vector<int> pre5 = {42};
    vector<int> in5  = {42};

    TreeNode* tree5 = buildFromPreorderInorder(pre5, in5);
    cout << "  Built tree:" << endl;
    printTree(tree5);
    cout << endl;

    // ─────────────────────────────────────────────
    // 說明 6: 為什麼 Preorder + Postorder 不唯一
    // ─────────────────────────────────────────────
    cout << "【6. Why Preorder + Postorder is NOT unique】\n" << endl;
    cout << "  Preorder:  [1, 2]" << endl;
    cout << "  Postorder: [2, 1]" << endl;
    cout << endl;
    cout << "  Possible tree A:     Possible tree B:" << endl;
    cout << "       1                    1" << endl;
    cout << "      /                      \\" << endl;
    cout << "     2                        2" << endl;
    cout << endl;
    cout << "  Both have the same Preorder and Postorder!" << endl;
    cout << "  Without Inorder, we cannot distinguish left from right." << endl;

    // 清理
    deleteTree(tree1);
    deleteTree(tree2);
    deleteTree(tree3);
    deleteTree(tree3b);
    deleteTree(tree4);
    deleteTree(tree5);

    cout << "\n============================================================" << endl;
    cout << "  Done." << endl;
    cout << "============================================================" << endl;

    return 0;
}