Skip to content

Commit cda64b1

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1110
No.1110.Delete Nodes And Return Forest
1 parent bc7e890 commit cda64b1

File tree

6 files changed

+537
-55
lines changed

6 files changed

+537
-55
lines changed

‎solution/1100-1199/1110.Delete Nodes And Return Forest/README.md

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,22 +45,233 @@
4545

4646
<!-- 这里可写通用的实现逻辑 -->
4747

48+
**方法一：后序遍历**
49+
50+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是树的节点数。
51+
4852
<!-- tabs:start -->
4953

5054
### **Python3**
5155

5256
<!-- 这里可写当前语言的特殊实现逻辑 -->
5357

5458
```python
59+
# Definition for a binary tree node.
60+
# class TreeNode:
61+
# def __init__(self, val=0, left=None, right=None):
62+
# self.val = val
63+
# self.left = left
64+
# self.right = right
65+
class Solution:
66+
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
67+
def dfs(fa, root):
68+
if root is None:
69+
return
70+
dfs(root, root.left)
71+
dfs(root, root.right)
72+
if root.val in s:
73+
if fa and fa.left == root:
74+
fa.left = None
75+
if fa and fa.right == root:
76+
fa.right = None
77+
if root.left:
78+
ans.append(root.left)
79+
if root.right:
80+
ans.append(root.right)
5581

82+
s = set(to_delete)
83+
ans = []
84+
if root.val not in s:
85+
ans.append(root)
86+
dfs(None, root)
87+
return ans
5688
```
5789

5890
### **Java**
5991

6092
<!-- 这里可写当前语言的特殊实现逻辑 -->
6193

6294
```java
95+
/**
96+
* Definition for a binary tree node.
97+
* public class TreeNode {
98+
* int val;
99+
* TreeNode left;
100+
* TreeNode right;
101+
* TreeNode() {}
102+
* TreeNode(int val) { this.val = val; }
103+
* TreeNode(int val, TreeNode left, TreeNode right) {
104+
* this.val = val;
105+
* this.left = left;
106+
* this.right = right;
107+
* }
108+
* }
109+
*/
110+
class Solution {
111+
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
112+
boolean[] del = new boolean[1001];
113+
for (int d : to_delete) {
114+
del[d] = true;
115+
}
116+
List<TreeNode> res = new ArrayList<>();
117+
dfs(root, true, del, res);
118+
return res;
119+
}
120+
121+
private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) {
122+
if (root == null) {
123+
return null;
124+
}
125+
boolean flag = del[root.val];
126+
if (!flag && isRoot) {
127+
res.add(root);
128+
}
129+
root.left = dfs(root.left, flag, del, res);
130+
root.right = dfs(root.right, flag, del, res);
131+
return flag ? null : root;
132+
}
133+
}
134+
```
135+
136+
```java
137+
/**
138+
* Definition for a binary tree node.
139+
* public class TreeNode {
140+
* int val;
141+
* TreeNode left;
142+
* TreeNode right;
143+
* TreeNode() {}
144+
* TreeNode(int val) { this.val = val; }
145+
* TreeNode(int val, TreeNode left, TreeNode right) {
146+
* this.val = val;
147+
* this.left = left;
148+
* this.right = right;
149+
* }
150+
* }
151+
*/
152+
class Solution {
153+
private List<TreeNode> ans = new ArrayList<>();
154+
private Set<Integer> s = new HashSet<>();
155+
156+
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
157+
for (int v : to_delete) {
158+
s.add(v);
159+
}
160+
if (!s.contains(root.val)) {
161+
ans.add(root);
162+
}
163+
dfs(null, root);
164+
return ans;
165+
}
166+
167+
private void dfs(TreeNode fa, TreeNode root) {
168+
if (root == null) {
169+
return;
170+
}
171+
dfs(root, root.left);
172+
dfs(root, root.right);
173+
if (s.contains(root.val)) {
174+
if (fa != null && fa.left == root) {
175+
fa.left = null;
176+
}
177+
if (fa != null && fa.right == root) {
178+
fa.right = null;
179+
}
180+
if (root.left != null) {
181+
ans.add(root.left);
182+
}
183+
if (root.right != null) {
184+
ans.add(root.right);
185+
}
186+
}
187+
}
188+
}
189+
```
190+
191+
### **C++**
192+
193+
```cpp
194+
/**
195+
* Definition for a binary tree node.
196+
* struct TreeNode {
197+
* int val;
198+
* TreeNode *left;
199+
* TreeNode *right;
200+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
201+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
202+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
203+
* };
204+
*/
205+
class Solution {
206+
public:
207+
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
208+
vector<TreeNode*> ans;
209+
unordered_set<int> s(to_delete.begin(), to_delete.end());
210+
if (!s.count(root->val)) ans.push_back(root);
211+
dfs(nullptr, root, s, ans);
212+
return ans;
213+
}
214+
215+
void dfs(TreeNode* fa, TreeNode* root, unordered_set<int>& s, vector<TreeNode*>& ans) {
216+
if (!root) return;
217+
dfs(root, root->left, s, ans);
218+
dfs(root, root->right, s, ans);
219+
if (s.count(root->val)) {
220+
if (fa && fa->left == root) fa->left = nullptr;
221+
if (fa && fa->right == root) fa->right = nullptr;
222+
if (root->left) ans.push_back(root->left);
223+
if (root->right) ans.push_back(root->right);
224+
}
225+
}
226+
};
227+
```
228+
229+
### **Go**
63230

231+
```go
232+
/**
233+
* Definition for a binary tree node.
234+
* type TreeNode struct {
235+
* Val int
236+
* Left *TreeNode
237+
* Right *TreeNode
238+
* }
239+
*/
240+
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
241+
s := map[int]bool{}
242+
for _, v := range to_delete {
243+
s[v] = true
244+
}
245+
ans := []*TreeNode{}
246+
if !s[root.Val] {
247+
ans = append(ans, root)
248+
}
249+
var fa *TreeNode
250+
var dfs func(fa, root *TreeNode)
251+
dfs = func(fa, root *TreeNode) {
252+
if root == nil {
253+
return
254+
}
255+
dfs(root, root.Left)
256+
dfs(root, root.Right)
257+
if s[root.Val] {
258+
if fa != nil && fa.Left == root {
259+
fa.Left = nil
260+
}
261+
if fa != nil && fa.Right == root {
262+
fa.Right = nil
263+
}
264+
if root.Left != nil {
265+
ans = append(ans, root.Left)
266+
}
267+
if root.Right != nil {
268+
ans = append(ans, root.Right)
269+
}
270+
}
271+
}
272+
dfs(fa, root)
273+
return ans
274+
}
64275
```
65276

66277
### **...**

0 commit comments

Comments
 (0)