## Algorithm

Problem Name: 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]]
```

Example 2:

```Input: root = [1,2,4,null,3], to_delete = [3]
Output: [[1,2,4]]
```

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`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List delNodes(TreeNode root, int[] to_delete) {
List result = new ArrayList<>();
Set < Integer> deleteSet = Arrays.stream(to_delete).boxed().collect(Collectors.toSet());
helper(root, deleteSet, result, null);
return result;
}

private void helper(TreeNode node, Set < Integer> deleteSet, List result, TreeNode parent) {
if (node == null) {
return;
}
TreeNode nextParent = null;
if (deleteSet.contains(node.val)) {
if (parent != null) {
if (parent.left == node) {
parent.left = null;
} else {
parent.right = null;
}
}
} else {
if (parent == null) {
}
nextParent = node;
}
helper(node.left, deleteSet, result, nextParent);
helper(node.right, deleteSet, result, nextParent);
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,6,7], to_delete = [3,5]

Output

cmd
[[1,2,null,4],[6],[7]]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const delNodes = function(root, to_delete) {
let rst = []
let dfs = function(node, isRoot) {
if (!node) return
let isDel = to_delete.indexOf(node.val) !== -1
if (node.left) node.left = dfs(node.left, isDel)
if (node.right) node.right = dfs(node.right, isDel)
if (isRoot && !isDel) rst.push(node)
return isDel ? null : node
}
if (!root) return []
dfs(root, true)
return rst
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,6,7], to_delete = [3,5]

Output

cmd
[[1,2,null,4],[6],[7]]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:

def dfs(node, parent):
if not node: return True
dfs(node.left, node)
dfs(node.right, node)
if node.val in blacklist:
if parent and parent.left == node:
parent.left = None
elif parent:
parent.right = None
if node.left:
res.append(node.left)
if node.right:
res.append(node.right)
res = []
blacklist = set(to_delete)
dfs(root, None)
return res + [root] if root.val not in blacklist else res
``````
Copy The Code &

Input

cmd
root = [1,2,4,null,3], to_delete = [3]

Output

cmd
[[1,2,4]]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _1110_DeleteNodesAndReturnForest
{
public IList < TreeNode> DelNodes(TreeNode root, int[] to_delete)
{
var set = new HashSet<int>(to_delete);
var results = new List();

return results;
}

private void DeleteRoot(TreeNode node, TreeNode parent, HashSet < int> deleteSet, List results)
{
if (node == null) return;
DeleteRoot(node.left, node, deleteSet, results);
DeleteRoot(node.right, node, deleteSet, results);

if (deleteSet.Contains(node.val))
{

if (parent.left == node) parent.left = null;
else if (parent.right == node) parent.right = null;

deleteSet.Remove(node.val);
}
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,4,null,3], to_delete = [3]

Output

cmd
[[1,2,4]]