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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def createBinaryTree(self, descriptions):
9 nodeMap = {}
10 children = set()
11
12 for parent, child, isLeft in descriptions:
13 if parent not in nodeMap:
14 nodeMap[parent] = TreeNode(parent)
15 if child not in nodeMap:
16 nodeMap[child] = TreeNode(child)
17
18 if isLeft:
19 nodeMap[parent].left = nodeMap[child]
20 else:
21 nodeMap[parent].right = nodeMap[child]
22
23 children.add(child)
24
25 # Find the root
26 for key in nodeMap:
27 if key not in children:
28 return nodeMap[key]
29
30 return None
31The Python solution leverages a dictionary to track TreeNode instances and a set to identify nodes that have appeared as children. It iteratively constructs the tree based on the input descriptions, following direct mapping and reference updates.
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.