2196. Create Binary Tree From Descriptions

題目 / Problem

中文給你一個二維整數陣列 descriptions，其中每一項 descriptions[i] = [parentᵢ, childᵢ, isLeftᵢ] 表示在一棵「數值互不相同」的二元樹中，parentᵢ 是 childᵢ 的父節點：

若 isLeftᵢ == 1，則 childᵢ 是 parentᵢ 的左子節點。
若 isLeftᵢ == 0，則 childᵢ 是 parentᵢ 的右子節點。

請依照這些描述建出這棵二元樹，並回傳它的根節點。題目保證描述能組成一棵合法的二元樹。

English You are given a 2D integer array descriptions where each descriptions[i] = [parentᵢ, childᵢ, isLeftᵢ] says that, inside a binary tree of unique values, parentᵢ is the parent of childᵢ:

If isLeftᵢ == 1, childᵢ is the left child of parentᵢ.
If isLeftᵢ == 0, childᵢ is the right child of parentᵢ.

Build the described binary tree and return its root. The input is guaranteed to form a valid tree.

Constraints - 1 <= descriptions.length <= 10⁴ - descriptions[i].length == 3 - 1 <= parentᵢ, childᵢ <= 10⁵ - 0 <= isLeftᵢ <= 1 - The described tree is valid.

Worked example Input: [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] Output: [50,20,80,15,17,19] The root is 50 because no description ever lists 50 as a child.

名詞解釋 / Glossary

二元樹 / Binary tree：每個節點最多有兩個子節點（左、右）的樹狀結構 / A tree where each node has at most two children (left and right).
節點 / Node：樹的基本單位，這裡每個節點含一個整數值 val 與兩個指標 left、right / The basic unit of a tree; here each holds an integer val and two pointers left, right.
根節點 / Root：整棵樹最頂端、沒有父節點的節點 / The topmost node, the only one with no parent.
雜湊表 / Hash map（C++ unordered_map）：用「鍵 → 值」做平均 O(1) 查詢的容器；這裡用「節點值 → 節點指標」快速找到或建立節點 / A key→value container with average O(1) lookup; here it maps a value to its node pointer.
指標 / Pointer（C 的 TreeNode*）：儲存某塊記憶體位址的變數；用 -> 取出指向物件的成員，例如 node->left / A variable holding a memory address; -> accesses a member of the pointed-to object.
動態配置 / Dynamic allocation（C 的 malloc）：在執行期向系統要一塊記憶體來放一個節點 / Asking the OS for memory at runtime to store a node.
集合 / Set：只記錄「某值是否出現過」的容器；這裡用來標記「哪些值曾當過子節點」/ A container tracking membership; used here to mark which values appeared as a child.

思路

最直覺的做法是：每次拿到一筆 [parent, child, isLeft]，就去整棵已建好的樹裡找 parent 在哪裡，再把 child 掛上去。但「在樹裡找某個值」需要遍歷，最壞 O(n)，總共 O(n²)，當描述多達 10⁴ 筆時會太慢。問題的關鍵在於：節點可能以任意順序出現，例如先看到 [20,15,1]（孩子 15），但此時 20 自己都還沒被建出來。所以我們需要一種「不管先看到誰，都能立刻找到或建立對應節點」的機制——這正是雜湊表的用途。我們用一個 map 把「數值」對映到「節點指標」：每次需要某個值的節點時，就查 map，有就拿、沒有就 new（或 malloc）一個並存進 map。這樣連結父子只要 O(1)。建立連結時，依 isLeft 決定掛在 parent->left 還是 parent->right。最後一個問題是找根：根是「從來沒當過任何人的孩子」的那個值。我們額外用一個集合記錄所有出現過的 child，掃完描述後，唯一不在這個集合裡的父節點值就是根。整體只掃描描述兩次（或一次建表、一次找根），時間 O(n)。

The naive idea is: for each [parent, child, isLeft], search the partially-built tree for parent and attach child. But searching a tree for a value costs up to O(n), giving O(n²) overall — too slow for 10⁴ rows. The real difficulty is that nodes appear in arbitrary order: you might see [20,15,1] before 20 itself has ever been created. So we want a way to "find-or-create the node for any value instantly," which is exactly what a hash map gives us. We map each integer value to its node pointer; whenever we need a node, we look it up — reuse it if present, otherwise allocate a fresh node and store it. Linking parent to child is then O(1): set parent->left or parent->right based on isLeft. The final piece is identifying the root: it is the one value that is never listed as a child. We keep a set of every value that appears as a child; after processing, the single parent value not in that set is the root. We touch the data a constant number of times, so the whole thing is O(n).

逐步走查 / Walkthrough

Input: [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]] We maintain nodes (value → node) and children (set of values seen as a child).

Step	Row `[p,c,isLeft]`	Get/create `p`	Get/create `c`	Link	`children` after
1	`[20,15,1]`	create 20	create 15	`20.left = 15`	{15}
2	`[20,17,0]`	reuse 20	create 17	`20.right = 17`	{15,17}
3	`[50,20,1]`	create 50	reuse 20	`50.left = 20`	{15,17,20}
4	`[50,80,0]`	reuse 50	create 80	`50.right = 80`	{15,17,20,80}
5	`[80,19,1]`	reuse 80	create 19	`80.left = 19`	{15,17,20,80,19}

Find root / 找根：parent values seen are {20, 50, 80}. Among them, only 50 is not in children. So 50 is the root. ✅ Returning node 50 gives the tree [50,20,80,15,17,19].

Solution — C

/*
 * 演算法 / 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
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 用 unordered_map<int, TreeNode*> 做 find-or-create，邊讀描述邊連結父子；
 * 用一個集合記錄所有當過孩子的值，最後唯一不在集合裡的父節點值就是根。O(n)。
 * Use a hash map for find-or-create node lookup, link parent/child while reading,
 * track every child in a set; the parent never seen as a child is the root. O(n).
 */

// LeetCode 已提供 TreeNode / TreeNode is predefined:
// struct TreeNode { int val; TreeNode *left; TreeNode *right; ... };

class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        // 值 → 節點指標；unordered_map 平均 O(1) 查詢 / value→node, average O(1) lookups.
        unordered_map<int, TreeNode*> nodes;
        // 記錄所有當過孩子的值；之後用來排除非根節點 / set of every value seen as a child.
        unordered_set<int> children;

        // lambda：find-or-create，封裝「沒有就 new、有就重用」的邏輯 / find-or-create helper.
        // [&] 表示以參考方式捕捉外部變數（這裡是 nodes）/ [&] captures `nodes` by reference.
        auto getNode = [&](int val) -> TreeNode* {
            auto& slot = nodes[val];          // operator[] 不存在時自動建立一格(初值 nullptr) / inserts nullptr if absent
            if (!slot) slot = new TreeNode(val);  // 還是空就配置新節點 / allocate if still null
            return slot;                      // 回傳該節點 / return the node
        };

        // 範圍 for：依序取出每一筆描述 / range-for over each description.
        for (const auto& d : descriptions) {
            int p = d[0], c = d[1], isLeft = d[2];  // 拆出父、子、左右旗標 / unpack fields
            TreeNode* parent = getNode(p);          // 取得或建立父節點 / find-or-create parent
            TreeNode* child  = getNode(c);          // 取得或建立子節點 / find-or-create child
            if (isLeft) parent->left = child;       // isLeft==1 掛左 / attach as left child
            else        parent->right = child;      // isLeft==0 掛右 / attach as right child
            children.insert(c);                     // c 當過孩子，記下來 / record c as a child
        }

        // 找根：第一個「不是任何人孩子」的父節點 / root = the parent never used as a child.
        for (const auto& d : descriptions) {
            int p = d[0];                           // 父節點值 / parent value
            if (children.find(p) == children.end()) // 不在 children 集合中 / not found in children
                return nodes[p];                    // 它就是根 / it is the root
        }
        return nullptr;  // 理論上不會到這（題目保證有根）/ unreachable for valid input
    }
};

複雜度 / Complexity

Time: O(n) — n 是 descriptions 的筆數。每筆描述做常數次雜湊查詢與一次連結（平均 O(1)），找根也只多掃一遍，故總計線性。/ Each of the n rows does a constant number of average-O(1) map operations plus one link; finding the root is one more linear pass.
Space: O(n) — 雜湊表/集合最多存約 n 個不同的值，建出的樹也有 O(n) 個節點。/ The map, the set, and the allocated nodes each hold up to O(n) entries.

Pitfalls & Edge Cases

以為節點按順序出現 / Assuming nodes appear in order：父節點可能比它的孩子晚出現，所以不能「先建父再掛子」。find-or-create 讓順序不再重要。/ A parent may appear after its child, so you can't rely on creation order — find-or-create handles any order.
重複建立同一節點 / Creating duplicate nodes：同一個值在多筆描述中出現（一次當父、一次當子）。務必透過 map 重用，否則樹會斷開。/ The same value shows up as both a parent and a child; always reuse via the map or the tree splits apart.
找根的方式 / Finding the root：不要找「沒有父指標的節點」——所有節點初始都沒有父指標。正確判準是「從未出現在 child 欄位」。/ Don't look for a node lacking a parent pointer (all start that way); the root is the value never listed as a child.
C 的直接定址表大小 / Direct-address table size：值域到 10⁵，陣列要開 100001（含索引 10⁵），否則越界。用 calloc 確保初值為 NULL。/ Values reach 10⁵, so size the array 100001 and zero-init with calloc.
記憶體釋放 / Freeing memory：C 版可釋放輔助陣列，但不要 free 樹節點——那是回傳給 LeetCode 的結果。/ Free the helper arrays, but never free the tree nodes you return.