友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1110. 删点成林
给出二叉树的根节点 root，树上每个节点都有一个不同的值。
如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
返回森林中的每棵树。你可以按任意顺序组织答案。
示例 1：
输入：root = [1,2,3,4,5,6,7], to_delete = [3,5] 输出：[[1,2,null,4],[6],[7]]
示例 2：
输入：root = [1,2,4,null,3], to_delete = [3] 输出：[[1,2,4]]
提示：
-
树中的节点数最大为
1000。 -
每个节点都有一个介于
1到1000之间的值，且各不相同。 -
to_delete.length <= 1000 -
to_delete包含一些从1到1000、各不相同的值。
思路分析
-
一刷
-
二刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-27 15:06:39
*/
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
List<TreeNode> result = new ArrayList<>();
Set<Integer> deletes = Arrays.stream(to_delete)
.boxed().collect(Collectors.toUnmodifiableSet());
TreeNode tree = dfs(root, deletes, result);
if (tree != null) {
result.add(tree);
}
return result;
}
private TreeNode dfs(TreeNode root, Set<Integer> deletes, List<TreeNode> result) {
if (root == null) {
return null;
}
TreeNode left = dfs(root.left, deletes, result);
TreeNode right = dfs(root.right, deletes, result);
if (deletes.contains(root.val)) {
if (left != null) {
result.add(left);
}
if (right != null) {
result.add(right);
}
return null;
} else {
if (left == null) {
root.left = null;
}
if (right == null) {
root.right = null;
}
return root;
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-27 21:06:27
*/
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
Set<Integer> set = new HashSet<>(to_delete.length);
Arrays.stream(to_delete).forEach(set::add);
List<TreeNode> result = new ArrayList<>();
dfs(root, set, result, null, true);
return result;
}
private void dfs(TreeNode node, Set<Integer> set,
List<TreeNode> result, TreeNode parent, boolean left) {
if (node == null) {
return;
}
if (set.contains(node.val)) {
if (parent != null) {
if (left) {
parent.left = null;
} else {
parent.right = null;
}
}
dfs(node.left, set, result, null, true);
dfs(node.right, set, result, null, false);
} else {
if (parent == null) {
result.add(node);
}
dfs(node.left, set, result, node, true);
dfs(node.right, set, result, node, false);
}
}