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
The Java solution implements a similar strategy using a HashMap for storing TreeNode objects and a HashSet to track nodes that have been children. The solution iterates over descriptions to create and link nodes, identifying the root as a node not in the child set.
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.
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 # First pass: Create all nodes
13 for parent, child, isLeft in descriptions:
14 if parent not in nodeMap:
15 nodeMap[parent] = TreeNode(parent)
16 if child not in nodeMap:
17 nodeMap[child] = TreeNode(child)
18
19 children.add(child)
20
21 # Second pass: Link nodes
22 for parent, child, isLeft in descriptions:
23 if isLeft:
24 nodeMap[parent].left = nodeMap[child]
25 else:
26 nodeMap[parent].right = nodeMap[child]
27
28 # Find the root
29 for key in nodeMap:
30 if key not in children:
31 return nodeMap[key]
32
33 return None
34The 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.