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
In Java, this solution implements a similar approach: define nodes in an initial pass using the map for easy access and in a subsequent pass, populate the left and right relations for each node as specified by the descriptions list.