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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5typedef struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9} TreeNode;
10
11TreeNode* createNode(int val) {
12 TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
13 node->val = val;
14 node->left = NULL;
15 node->right = NULL;
16 return node;
17}
18
19TreeNode* createBinaryTree(int** descriptions, int descriptionsSize, int* descriptionsColSize) {
20 TreeNode* nodes[100000] = { NULL };
21 bool isChild[100000] = { false };
22
23 for (int i = 0; i < descriptionsSize; ++i) {
24 int parentVal = descriptions[i][0], childVal = descriptions[i][1], isLeft = descriptions[i][2];
25
26 if (nodes[parentVal] == NULL) {
27 nodes[parentVal] = createNode(parentVal);
28 }
29
30 if (nodes[childVal] == NULL) {
31 nodes[childVal] = createNode(childVal);
32 }
33
34 if (isLeft) {
35 nodes[parentVal]->left = nodes[childVal];
36 } else {
37 nodes[parentVal]->right = nodes[childVal];
38 }
39
40 isChild[childVal] = true;
41 }
42
43 for (int i = 0; i < 100000; ++i) {
44 if (nodes[i] != NULL && !isChild[i]) {
45 return nodes[i]; // This node is not a child, hence it must be the root
46 }
47 }
48
49 return NULL;
50}
51This solution in C creates a hash map using an array to store nodes and a boolean array to track which nodes have been identified as children. It creates nodes dynamically as needed and links them based on the description inputs. It finally identifies the root by finding a node that has not been marked as a child.
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 JavaScript implementation follows a similar approach by creating each necessary TreeNode object in advance. Nodes are linked by iterating over the description input, resulting in correct binary tree construction.