/*
 * 演算法 / Algorithm:
 * postorder 最後一個元素是根；在 inorder 中切成左/右子樹並遞迴。
 * The last postorder element is the root; split inorder into left/right and recurse.
 * 反向掃 postorder（根→右→左），先建右子樹，用 unordered_map 做 O(1) 根查詢。
 * Scan postorder backward (root,right,left), build right subtree first, O(1) lookup via unordered_map.
 */

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

// LeetCode 提供的節點定義 / node definition provided by LeetCode:
// struct TreeNode { int val; TreeNode *left; TreeNode *right;
//                   TreeNode(int x): val(x), left(nullptr), right(nullptr) {} };

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // unordered_map 是雜湊表：value -> inorder 索引，查詢平均 O(1) / hash map: value -> inorder index
        unordered_map<int, int> inIndex;
        for (int i = 0; i < (int)inorder.size(); i++)
            inIndex[inorder[i]] = i;            // 記下每個值的位置 / record each value's position

        int postIdx = (int)postorder.size() - 1; // 從尾端開始的指標 / pointer starting at the tail

        // lambda：可遞迴的區域函式；捕捉 (&) 外部變數的參考以便修改 postIdx / recursive lambda capturing by reference
        // 用 auto&& self 讓 lambda 能呼叫自己（C++ 遞迴 lambda 慣用寫法）/ self-reference trick for recursion
        auto build = [&](auto&& self, int inLeft, int inRight) -> TreeNode* {
            if (inLeft > inRight)               // 空區間 => 沒有節點 / empty range => no node
                return nullptr;                 // nullptr 表示空子樹 / nullptr = empty subtree

            int rootVal = postorder[postIdx--]; // 取根後指標前移；post-decrement 先用值再減 / take root then move pointer left
            TreeNode* root = new TreeNode(rootVal); // new 在堆上建立節點 / allocate node on the heap

            int rootPos = inIndex[rootVal];     // O(1) 找到根在 inorder 的位置 / O(1) root position in inorder

            // 先右後左，對應 postorder 反向讀取順序 / right before left, matching backward postorder
            root->right = self(self, rootPos + 1, inRight); // 右子樹 / right subtree
            root->left  = self(self, inLeft, rootPos - 1);  // 左子樹 / left subtree

            return root;                        // 回傳子樹根 / return subtree root
        };

        return build(build, 0, (int)inorder.size() - 1); // 對整段中序建樹 / build over the full inorder range
    }
};