-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDeleteNodesAndReturnForest.java
More file actions
91 lines (83 loc) · 2.22 KB
/
Copy pathDeleteNodesAndReturnForest.java
File metadata and controls
91 lines (83 loc) · 2.22 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
package tree;
import utils.LeetCode;
import utils.Level;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 1110. Delete Nodes And Return Forest
* Medium
*
* 1451
*
* 48
*
* Add to List
*
* Share
* 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 1 and 1000.
* to_delete.length <= 1000
* to_delete contains distinct values between 1 and 1000
*/
/**
* 111 / 111 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 39.5 MB
*/
@LeetCode(no = 1110,
level = Level.MEDIUM,
url = "https://leetcode.com/problems/delete-nodes-and-return-forest/",
title = "Delete Nodes And Return Forest"
)
public class DeleteNodesAndReturnForest {
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
List<TreeNode> nodes = new ArrayList<>();
if (root == null) return nodes;
Set<Integer> nodesToDelete = new HashSet<>();
for (int i : to_delete) {
nodesToDelete.add(i);
}
delNodes(root, nodesToDelete, nodes);
if (!nodesToDelete.contains(root.val)) {
nodes.add(root);
}
return nodes;
}
TreeNode delNodes(TreeNode node, Set<Integer> nodesToDelete, List<TreeNode> res) {
if (node == null)
return null;
node.left = delNodes(node.left, nodesToDelete, res);
node.right = delNodes(node.right, nodesToDelete, res);
if (node != null) {
if (nodesToDelete.contains(node.val)) {
if (node.left != null)
res.add(node.left);
if (node.right != null)
res.add(node.right);
node = null;
}
}
return node;
}
}