/*
 * 演算法 / Algorithm:
 * 前序第一個元素是根；在中序中找到根的位置，左邊是左子樹、右邊是右子樹。
 * The first preorder element is the root; its position in inorder splits
 * inorder into left/right subtrees. Recurse on index ranges (no array copying).
 * 用雜湊表把「值 → 中序索引」預先記下，讓每次找根為 O(1)，總體 O(n)。
 * A value→inorder-index hash map makes each root lookup O(1), giving O(n) total.
 */

// LeetCode 提供的樹節點定義（此處僅為說明，實際由平台給出）
// LeetCode-provided node struct (shown for reference):
struct TreeNode {
    int val;                 // 節點存的整數 / the integer stored in this node
    struct TreeNode *left;   // 指向左子節點的指標 / pointer to the left child
    struct TreeNode *right;  // 指向右子節點的指標 / pointer to the right child
};

#include <stdlib.h>  // 需要 malloc / needed for malloc

// 值的範圍是 -3000..3000，共 6001 個可能值。用陣列當雜湊表最簡單快速。
// Values range -3000..3000 (6001 possibilities); a plain array is the simplest, fastest map.
// 索引 = 值 + 3000（把負數平移成非負）/ index = value + 3000 (shift negatives into [0,6000]).
#define OFFSET 3000                     // 平移量 / the shift amount
#define MAP_SIZE 6001                   // 陣列大小 / size of the lookup array

// 遞迴輔助函式：用給定的索引範圍建一棵子樹。
// Recursive helper: build one subtree from the given index ranges.
// idxMap[v+OFFSET] = v 在 inorder 中的位置 / position of value v inside inorder.
static struct TreeNode* build(int* preorder, int preStart, int preEnd,
                              int inStart, int inEnd, int* idxMap) {
    // 範圍為空表示沒有節點，回傳 NULL（空子樹）。
    // An empty range means no node here → return NULL (empty subtree).
    if (preStart > preEnd) {
        return NULL;
    }

    // 前序的第一個元素就是這棵（子）樹的根值。
    // The first element of this preorder slice is this subtree's root value.
    int rootVal = preorder[preStart];

    // 配置一個新節點；malloc 向系統要一塊記憶體，回傳指向它的指標。
    // Allocate a new node; malloc requests memory and returns a pointer to it.
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = rootVal;    // 設定節點值 / set the node's value
    root->left = NULL;      // 先設空，稍後可能覆寫 / default empty, may be overwritten
    root->right = NULL;     // 先設空 / default empty

    // O(1) 從雜湊表查出根在中序中的位置。
    // O(1) lookup of the root's position in inorder via the map.
    int inRoot = idxMap[rootVal + OFFSET];

    // 中序中根左邊的元素個數 = 左子樹的節點數。
    // Number of elements left of the root in inorder = size of the left subtree.
    int leftSize = inRoot - inStart;

    // 建左子樹：前序取根之後的 leftSize 個元素；中序取根左邊那段。
    // Build left subtree: preorder = the leftSize elements after root; inorder = left part.
    root->left = build(preorder,
                       preStart + 1, preStart + leftSize,  // 前序左子樹範圍 / preorder range
                       inStart, inRoot - 1,                // 中序左子樹範圍 / inorder range
                       idxMap);

    // 建右子樹：前序取剩下的元素；中序取根右邊那段。
    // Build right subtree: preorder = remaining elements; inorder = right part.
    root->right = build(preorder,
                        preStart + leftSize + 1, preEnd,   // 前序右子樹範圍 / preorder range
                        inRoot + 1, inEnd,                 // 中序右子樹範圍 / inorder range
                        idxMap);

    return root;  // 回傳建好的（子）樹根 / return the built subtree root
}

// LeetCode 入口函式；簽名固定。preorderSize、inorderSize 是陣列長度。
// LeetCode entry function; fixed signature. preorderSize/inorderSize are array lengths.
struct TreeNode* buildTree(int* preorder, int preorderSize,
                           int* inorder, int inorderSize) {
    // 空輸入直接回傳空樹（依約束不會發生，但保險起見）。
    // Empty input → empty tree (won't happen per constraints, but safe to guard).
    if (preorderSize == 0) {
        return NULL;
    }

    // 建立「值 → 中序索引」的雜湊表。
    // Build the value→inorder-index map.
    // 用 malloc 配置陣列；每個 int 存一個索引 / allocate an int array to hold indices.
    int* idxMap = (int*)malloc(sizeof(int) * MAP_SIZE);

    // 掃一遍 inorder，把每個值的位置記進 idxMap。
    // Scan inorder once, recording each value's position into idxMap.
    for (int i = 0; i < inorderSize; i++) {
        // inorder[i] + OFFSET 把值平移成合法陣列索引 / shift value to a valid index.
        idxMap[inorder[i] + OFFSET] = i;
    }

    // 從整個陣列範圍開始遞迴建樹。
    // Start recursion over the full index ranges.
    struct TreeNode* root = build(preorder, 0, preorderSize - 1,
                                  0, inorderSize - 1, idxMap);

    // 釋放雜湊表記憶體，避免記憶體洩漏。
    // Free the map memory to avoid a memory leak.
    free(idxMap);

    return root;  // 回傳整棵樹的根 / return the whole tree's root
}