2196. Create Binary Tree From Descriptions

Hint

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions)
    {
        // Map to store TreeNode pointers by their values
        // Set to keep track of all child nodes

        // Iterate over each description in the input
        for ()
        {
            // Parent node value
            // Child node value
            // Indicates if the child is a left child

            // If parent node is not already created, create it and store in nodeMap

            // If child node is not already created, create it and store in nodeMap

            // Attach the child to the appropriate side of the parent
            
            // Add the child value to the set of children
        }

        // Find and return the root node (a node that is not anyone's child)
        for ()
        {
            // If the value is not found in children set, it's the root
        }
        // If no root is found (though the problem guarantees there will be one), return nullptr
    }
};

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions)
    {
        // Map to store TreeNode pointers by their values
        unordered_map<int, TreeNode*> nodeMap;
        
        // Set to keep track of all child nodes
        unordered_set<int> children;

        // Iterate over each description in the input
        for (const auto& description : descriptions)
        {
            // Parent node value
            int parentValue = description[0];

            // Child node value
            int childValue = description[1];

            // Indicates if the child is a left child
            bool isLeft = description[2];

            // If parent node is not already created, create it and store in nodeMap
            if (!nodeMap.count(parentValue))
            {
                nodeMap[parentValue] = new TreeNode(parentValue);
            }

            // If child node is not already created, create it and store in nodeMap
            if (!nodeMap.count(childValue))
            {
                nodeMap[childValue] = new TreeNode(childValue);
            }

            // Attach the child to the appropriate side of the parent
            if (isLeft)
            {
                nodeMap[parentValue]->left = nodeMap[childValue];
            }
            else
            {
                nodeMap[parentValue]->right = nodeMap[childValue];
            }

            // Add the child value to the set of children
            children.insert(childValue);
        }

        // Find and return the root node (a node that is not anyone's child)
        for (auto& entry : nodeMap)
        {
            auto& value = entry.first;
            auto& node = entry.second;
            
            // If the value is not found in children set, it's the root
            if (!children.count(value))
            {
                return node;
            }
        }

        // If no root is found (though the problem guarantees there will be one), return nullptr
        return nullptr;
    }
};

• 時間複雜度：
  $O(n)$
• 空間複雜度：
  $O(n)$