/*
 * 演算法 / Algorithm:
 * preorder[0] 是根；在 inorder 找到它，左邊為左子樹、右邊為右子樹，遞迴建樹。
 * preorder[0] is the root; locate it in inorder to split into left/right subtrees, recurse.
 * 用 unordered_map 記「值→中序索引」讓查找 O(1)，總複雜度 O(n)。
 * An unordered_map (value→inorder index) makes lookups O(1), giving O(n) overall.
 */

#include <vector>
#include <unordered_map>
using namespace std;

// LeetCode 的節點定義（此處僅供參考）/ LeetCode's node definition (for reference):
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// };

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // unordered_map 是雜湊表，平均 O(1) 查找 / hash map with average O(1) lookup.
        // key = 值, value = 它在 inorder 的索引 / key = value, value = its index in inorder.
        unordered_map<int, int> idxMap;

        // range-for 逐一走訪 inorder 的索引 / range-based loop over inorder indices.
        for (int i = 0; i < (int)inorder.size(); i++) {
            idxMap[inorder[i]] = i;  // 記錄每個值的位置 / record each value's position
        }

        // 從整個範圍開始遞迴建樹 / start recursion over the full ranges.
        return build(preorder, 0, (int)preorder.size() - 1,
                     0, (int)inorder.size() - 1, idxMap);
    }

private:
    // 遞迴輔助函式：用索引範圍建一棵子樹 / recursive helper building one subtree by ranges.
    // idxMap 以參考 (&) 傳入，避免複製整張表 / passed by reference (&) to avoid copying the map.
    TreeNode* build(const vector<int>& preorder, int preStart, int preEnd,
                    int inStart, int inEnd, unordered_map<int, int>& idxMap) {
        // 範圍為空 → 空子樹 / empty range → empty subtree.
        if (preStart > preEnd) {
            return nullptr;
        }

        // 前序第一個元素是根值 / first preorder element is the root value.
        int rootVal = preorder[preStart];

        // new 在堆積上建立節點並回傳指標 / new allocates a node on the heap, returns a pointer.
        TreeNode* root = new TreeNode(rootVal);

        // O(1) 查出根在中序的位置 / O(1) lookup of root's index in inorder.
        int inRoot = idxMap[rootVal];

        // 根左邊的元素個數 = 左子樹大小 / count left of root = size of left subtree.
        int leftSize = inRoot - inStart;

        // 建左子樹：前序取接下來 leftSize 個、中序取左段。
        // Build left subtree: next leftSize preorder elements; left inorder segment.
        root->left = build(preorder,
                           preStart + 1, preStart + leftSize,
                           inStart, inRoot - 1,
                           idxMap);

        // 建右子樹：前序取其餘元素、中序取右段。
        // Build right subtree: remaining preorder elements; right inorder segment.
        root->right = build(preorder,
                            preStart + leftSize + 1, preEnd,
                            inRoot + 1, inEnd,
                            idxMap);

        return root;  // 回傳這棵子樹的根 / return this subtree's root
    }
};