根据描述创建二叉树Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外：
- 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。
- 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。
请你根据 descriptions 的描述来构造二叉树并返回其 根节点 。
测试用例会保证可以构造出 有效 的二叉树。
示例 1：
输入：descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
输出：[50,20,80,15,17,19]
解释：根节点是值为 50 的节点，因为它没有父节点。
结果二叉树如上图所示。 示例 2：
输入：descriptions = [[1,2,1],[2,3,0],[3,4,1]]
输出：[1,2,null,null,3,4]
解释：根节点是值为 1 的节点，因为它没有父节点。
结果二叉树如上图所示。
提示：
- 1 <= descriptions.length <= 104
- descriptions[i].length == 3
- 1 <= parenti, childi <= 105
- 0 <= isLefti <= 1
- descriptions 所描述的二叉树是一棵有效二叉树
# 思路
// Hash记录所有节点，在迭代中创建和挂载节点。
# 解法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// Hash记录所有节点，在迭代中创建和挂载节点。
public TreeNode createBinaryTree(int[][] descriptions) {
Set<Integer> parents = new HashSet<>();
Set<Integer> children = new HashSet<>();
Map<Integer, TreeNode> map = new HashMap<>();
for (int[] item : descriptions) {
if (!children.contains(item[0])) {
parents.add(item[0]);
}
parents.remove(item[1]);
children.add(item[1]);
map.put(item[0], map.getOrDefault(item[0], new TreeNode(item[0])));
map.put(item[1], map.getOrDefault(item[1], new TreeNode(item[1])));
if (item[2] == 1) {
map.get(item[0]).left = map.get(item[1]);
} else {
map.get(item[0]).right = map.get(item[1]);
}
}
return map.get(new ArrayList<Integer>(parents).get(0));
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 总结
- 分析出几种情况，然后分别对各个情况实现
