友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1110. Delete Nodes And Return Forest
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]Constraints:
-
The number of nodes in the given tree is at most
1000. -
Each node has a distinct value between
1and1000. -
to_delete.length ⇐ 1000 -
to_deletecontains distinct values between1and1000.
思路分析
利用递归，在“后序遍历”阶段，对当前阶段判断是否需要删除。
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;
}
}