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