Sponsored
Sponsored
This approach uses a hash map to create nodes and establish their parent-child relationships. The root node is determined by finding nodes that haven't been a child in any relationship.
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6class TreeNode {
7public:
8 int val;
9 TreeNode* left;
10 TreeNode* right;
11 TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
12};
13
14class Solution {
15public:
16 TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
17 unordered_map<int, TreeNode*> nodes;
18 unordered_set<int> children;
19
20 for (const auto& desc : descriptions) {
21 int parent = desc[0], child = desc[1], isLeft = desc[2];
22 if (nodes.find(parent) == nodes.end())
23 nodes[parent] = new TreeNode(parent);
24 if (nodes.find(child) == nodes.end())
25 nodes[child] = new TreeNode(child);
26
27 if (isLeft) {
28 nodes[parent]->left = nodes[child];
29 } else {
30 nodes[parent]->right = nodes[child];
31 }
32
33 children.insert(child);
34 }
35
36 for (const auto& [key, node] : nodes) {
37 if (children.find(key) == children.end()) {
38 return node;
39 }
40 }
41
42 return nullptr;
43 }
44};
45The C++ solution utilizes unordered_map to maintain mappings of node values to their TreeNode pointers. An unordered_set keeps track of all child nodes, and the tree is constructed by iterating over descriptions and linking the nodes.
This approach uses a two-pass algorithm: the first pass creates all nodes independently, and the second pass links them based on the descriptive relationships. This avoids simultaneous creation and linking, providing a clearer separation of concerns between node creation and linkage.
Time Complexity: O(N), where N is the number of descriptions.
Space Complexity: O(V), where V is the number of unique nodes.
1
This C solution divides the node creation and linking into two separate passes. It allocates the nodes in the first pass and establishes the links between them in the second pass. This approach simplifies the code logic and ensures the nodes are available when linking operations occur.