Leetcode 2196 - Create Binary Tree From Descriptions

// Credit: https://leetcode.com/hank55663/ from https://leetcode.com/contest/weekly-contest-283/ranking/ problem C
// Added comment
class Solution {
public:
    int l[100005],r[100005]; // l[i] -> i 的左子節點; r[i] -> i 的右子節點. 0 代表沒有
    int cnt[100005]; // 當過 child 的次數
    TreeNode *build(int x){
        TreeNode *res = new TreeNode(x);
        if(l[x])
            res->left = build(l[x]);
        if(r[x])
            res->right = build(r[x]);
        return res;
    }
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        // init
        for(auto it:descriptions){
            l[it[0]] = r[it[0]] = l[it[1]] = r[it[1]] = 0;
        }

        // 建表
        for(auto it:descriptions){
            if(it[2])
                l[it[0]] = it[1];
            else
                r[it[0]] = it[1];
            cnt[it[1]]++;
        }

        // 建樹
        for(auto it:descriptions){
            if(cnt[it[0]] == 0){ // 如果沒當過 child => 是 root
                return build(it[0]);
            }
        }
        return NULL;
    }
};