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.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int val) { this.val = val; }
8}
9
10class Solution {
11 public TreeNode createBinaryTree(int[][] descriptions) {
12 Map<Integer, TreeNode> nodeMap = new HashMap<>();
13 Set<Integer> children = new HashSet<>();
14
15 for (int[] desc : descriptions) {
16 int parent = desc[0], child = desc[1], isLeft = desc[2];
17 nodeMap.putIfAbsent(parent, new TreeNode(parent));
18 nodeMap.putIfAbsent(child, new TreeNode(child));
19
20 if (isLeft == 1) {
21 nodeMap.get(parent).left = nodeMap.get(child);
22 } else {
23 nodeMap.get(parent).right = nodeMap.get(child);
24 }
25
26 children.add(child);
27 }
28
29 for (int key : nodeMap.keySet()) {
30 if (!children.contains(key)) {
31 return nodeMap.get(key);
32 }
33 }
34
35 return null;
36 }
37}
38The 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.
1
The 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.