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
1and1000. to_delete.length <= 1000to_deletecontains distinct values between1and1000.
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) {
result.add(node);
}
nextParent = node;
}
helper(node.left, deleteSet, result, nextParent);
helper(node.right, deleteSet, result, nextParent);
}
}
Input
root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output
[[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
}
Input
root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output
[[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
Input
root = [1,2,4,null,3], to_delete = [3]
Output
[[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();
var dummyHead = new TreeNode(-1);
dummyHead.left = root;
DeleteRoot(root, dummyHead, set, results);
if (dummyHead.left != null)
results.Add(root);
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 (node.left != null) results.Add(node.left);
if (node.right != null) results.Add(node.right);
if (parent.left == node) parent.left = null;
else if (parent.right == node) parent.right = null;
deleteSet.Remove(node.val);
}
}
}
}
Input
root = [1,2,4,null,3], to_delete = [3]
Output
[[1,2,4]]