/*
 * 演算法 / Algorithm:
 * 後序陣列最後一個元素是根；在中序陣列中找到它，左邊是左子樹、右邊是右子樹。
 * The last postorder element is the root; split inorder at it into left/right subtrees.
 * 從後往前讀 postorder（根→右→左），先建右子樹再建左子樹，用雜湊表 O(1) 查根位置。
 * Walk postorder backward, build right subtree before left, use a hash map for O(1) root lookup.
 */

// LeetCode 已定義好的節點結構（此處僅示意，實際由平台提供）/ node struct provided by LeetCode:
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

#include <stdlib.h>  // malloc 記憶體配置 / for malloc

// 值域是 -3000..3000，共 6001 個可能值；用位移把值變成非負索引 / shift values into a non-negative array index
#define OFFSET 3000                 // 把 -3000 對到 0 / maps -3000 to array slot 0
#define RANGE  6001                 // 可能值的總數 / total number of distinct possible values

// 全域的「值 -> 中序索引」查表，取代 hash map；索引 = 值 + OFFSET / value -> inorder index lookup
static int inIndexOf[RANGE];
// 全域指標：目前後序陣列從尾端往前掃到哪裡 / global pointer scanning postorder from the back
static int postIdx;
// 記住 postorder 陣列的起點，遞迴中直接取用 / remember postorder base pointer for the recursion
static int *postArr;

// 遞迴建樹：負責中序區間 [inLeft, inRight] 這段所代表的子樹 / build subtree covering inorder[inLeft..inRight]
static struct TreeNode *build(int inLeft, int inRight) {
    if (inLeft > inRight)           // 區間為空 => 沒有節點 / empty range means no node here
        return NULL;                // 回傳空指標表示「沒有子樹」/ NULL = no subtree

    int rootVal = postArr[postIdx]; // 目前後序指標指向的值就是這段的根 / current postorder value is this subtree's root
    postIdx--;                      // 用掉一個根，指標往前一格 / consume it, move pointer left

    // 配置一個新節點；malloc 回傳一塊未初始化的記憶體 / allocate one uninitialized node
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = rootVal;            // 設定節點值；-> 是「透過指標存取成員」/ set value; -> dereferences a pointer field

    // 根在中序陣列的位置：O(1) 查表，避免線性搜尋 / root's position in inorder via O(1) lookup
    int rootPos = inIndexOf[rootVal + OFFSET];

    // 關鍵順序：先建右子樹！因為 postorder 反著讀是 根->右->左 / build RIGHT first (backward postorder = root,right,left)
    root->right = build(rootPos + 1, inRight);  // 右子樹的中序在根的右邊 / right subtree is to the right of root
    root->left  = build(inLeft, rootPos - 1);   // 左子樹的中序在根的左邊 / left subtree is to the left of root

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

struct TreeNode *buildTree(int *inorder, int inorderSize,
                           int *postorder, int postorderSize) {
    // 先把「每個中序值 -> 它的索引」記進查表 / record each inorder value's index into the lookup table
    for (int i = 0; i < inorderSize; i++)
        inIndexOf[inorder[i] + OFFSET] = i;     // 值 + OFFSET 當作陣列下標 / value+OFFSET used as array subscript

    postArr = postorder;            // 讓遞迴函式能存取 postorder / expose postorder to the recursion
    postIdx = postorderSize - 1;    // 從最後一個元素開始（整棵樹的根）/ start at the last element (whole-tree root)

    return build(0, inorderSize - 1); // 整段中序區間對應整棵樹 / full inorder range = whole tree
}