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
The Python implementation separates creation and linking stages into two passes. Initial dictionary setup covers all potential nodes while recognizing child nodes, then linkage development iterates through ensuring accurate relationship formation.