create-binary-tree-from-descriptions.cpp

// Time:  O(n)
// Space: O(n)

// tree
class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        unordered_map<int, TreeNode *> nodes;
        unordered_set<int> children;
        for (const auto& d : descriptions) {
            if (!nodes.count(d[0])) {
                nodes[d[0]] = new TreeNode(d[0]);
            }
            if (!nodes.count(d[1])) {
                nodes[d[1]] = new TreeNode(d[1]);
            }
            if (d[2]) {
                nodes[d[0]]->left = nodes[d[1]];
            } else {
                nodes[d[0]]->right = nodes[d[1]];
            }
            children.emplace(d[1]);
        }
        for (const auto& [k, v] : nodes) {
            if (!children.count(k)) {
                return v;
            }
        }
        return nullptr;
    }
};