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