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