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
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.