/*
 * 演算法 / Algorithm:
 * 用雜湊表把「節點值」對映到「節點指標」，邊掃描描述邊 find-or-create 節點並連結父子；
 * 另用一個布林表記錄哪些值當過孩子，最後唯一沒當過孩子的父節點就是根。時間 O(n)。
 * Map value→node, find-or-create nodes while linking, mark every child;
 * the one parent never marked as a child is the root. O(n).
 */

// LeetCode 已提供 TreeNode 定義 / TreeNode is provided by LeetCode:
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

#define MAXV 100001  // 值的範圍是 1..1e5，陣列大小要能容納最大值 / values are 1..1e5

// 用「直接定址」的陣列當雜湊表：索引就是節點值，省去雜湊函式 / direct-address table:
// the value itself is the index, so no hash function is needed.
// 回傳值對應的節點；若不存在就建立一個新節點存進表中 / find-or-create the node for `val`.
static struct TreeNode* getNode(struct TreeNode** table, int val) {
    if (table[val] == NULL) {                                  // 表中還沒有這個值 / not created yet
        struct TreeNode* n = malloc(sizeof(struct TreeNode));  // 向系統要一塊記憶體 / allocate one node
        n->val = val;                                          // 設定節點數值 / set its value
        n->left = NULL;                                        // 初始無左子 / no left child yet
        n->right = NULL;                                       // 初始無右子 / no right child yet
        table[val] = n;                                        // 存進表，下次可重用 / store for reuse
    }
    return table[val];                                         // 回傳（剛建的或已存在的）/ return node
}

struct TreeNode* createBinaryTree(int** descriptions, int descriptionsSize,
                                  int* descriptionsColSize) {
    // calloc 會把每格初始化為 0（即 NULL），代表「尚未建立」/ calloc zero-fills => all NULL.
    struct TreeNode** table = calloc(MAXV, sizeof(struct TreeNode*)); // 值 → 節點 / value→node
    char* isChild = calloc(MAXV, sizeof(char));  // 標記某值是否當過孩子 / has this value been a child?

    for (int i = 0; i < descriptionsSize; i++) {       // 逐筆處理描述 / process each description
        int p = descriptions[i][0];                    // 父節點值 / parent value
        int c = descriptions[i][1];                    // 子節點值 / child value
        int isLeft = descriptions[i][2];               // 1=左, 0=右 / 1=left, 0=right

        struct TreeNode* parent = getNode(table, p);   // 取得或建立父節點 / find-or-create parent
        struct TreeNode* child  = getNode(table, c);   // 取得或建立子節點 / find-or-create child

        if (isLeft) parent->left = child;              // 掛成左子 / attach as left child
        else        parent->right = child;             // 掛成右子 / attach as right child

        isChild[c] = 1;                                // c 出現在 child 欄位，標記之 / c is a child
    }

    struct TreeNode* root = NULL;                      // 預備存放根節點 / will hold the root
    for (int i = 0; i < descriptionsSize; i++) {       // 在所有父節點中找根 / scan parents for root
        int p = descriptions[i][0];                    // 某個父節點值 / a parent value
        if (!isChild[p]) {                             // 它從沒當過孩子 => 它就是根 / never a child => root
            root = table[p];                           // 取出對應節點 / grab its node
            break;                                     // 找到一個就夠了 / only one root exists
        }
    }

    free(table);     // 釋放雜湊表本身（節點記憶體交給 LeetCode 處理）/ free the table array
    free(isChild);   // 釋放標記陣列 / free the marker array
    return root;     // 回傳根節點 / return the root
}