##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1110.html

# 1110. Delete Nodes And Return Forest (Medium)

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.

Related Topics:
Tree, Depth-first Search

## Solution 1.

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
if (root == null)
return new ArrayList<TreeNode>();
Set<Integer> deleteSet = new HashSet<Integer>();
for (int value : to_delete)
List<TreeNode> nodesList = new ArrayList<TreeNode>();
Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left, right = node.right;
if (left != null) {
map.put(left, node);
queue.offer(left);
}
if (right != null) {
map.put(right, node);
queue.offer(right);
}
}
List<TreeNode> forest = new ArrayList<TreeNode>();
if (!deleteSet.contains(root.val))
for (int i = nodesList.size() - 1; i >= 0 && !deleteSet.isEmpty(); i--) {
TreeNode node = nodesList.get(i);
if (deleteSet.contains(node.val)) {
TreeNode parent = map.get(node);
if (parent != null) {
if (node == parent.left)
parent.left = null;
else if (node == parent.right)
parent.right = null;
}
TreeNode left = node.left, right = node.right;
if (left != null)
if (right != null)
deleteSet.remove(node.val);
}
}
return forest;
}
}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
boolean[] del = new boolean[1001];
for (int d : to_delete) {
del[d] = true;
}
List<TreeNode> res = new ArrayList<>();
dfs(root, true, del, res);
return res;
}

private TreeNode dfs(TreeNode root, boolean isRoot, boolean[] del, List<TreeNode> res) {
if (root == null) {
return null;
}
boolean flag = del[root.val];
if (!flag && isRoot) {
}
root.left = dfs(root.left, flag, del, res);
root.right = dfs(root.right, flag, del, res);
return flag ? null : root;
}
}

• // OJ: https://leetcode.com/problems/delete-nodes-and-return-forest/
// Time: O(N)
// Space: O(D + H)
class Solution {
vector<TreeNode*> ans;
unordered_set<int> s;
void dfs(TreeNode *root, TreeNode *p = NULL) {
if (!root) return;
dfs(root->left, root);
dfs(root->right, root);
if (s.count(root->val)) {
if (p != NULL) {
if (p->left == root) p->left = NULL;
else p->right = NULL;
}
if (root->left) ans.push_back(root->left);
if (root->right) ans.push_back(root->right);
} else if (p == NULL) ans.push_back(root);
}
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
s = unordered_set<int>(begin(to_delete), end(to_delete));
dfs(root);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
def dfs(fa, root):
if root is None:
return
dfs(root, root.left)
dfs(root, root.right)
if root.val in s:
if fa and fa.left == root:
fa.left = None
if fa and fa.right == root:
fa.right = None
if root.left:
ans.append(root.left)
if root.right:
ans.append(root.right)

s = set(to_delete)
ans = []
if root.val not in s:
ans.append(root)
dfs(None, root)
return ans

############

# 1110. Delete Nodes And Return Forest
# https://leetcode.com/problems/delete-nodes-and-return-forest/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
res = []
delete = set(to_delete)

def dfs(node, is_root):
if not node: return None

to_delete = node.val in delete

if is_root and not to_delete:
res.append(node)

node.left = dfs(node.left, to_delete)
node.right = dfs(node.right, to_delete)

return None if to_delete else node

dfs(root, True)

return res


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
s := map[int]bool{}
for _, v := range to_delete {
s[v] = true
}
ans := []*TreeNode{}
if !s[root.Val] {
ans = append(ans, root)
}
var fa *TreeNode
var dfs func(fa, root *TreeNode)
dfs = func(fa, root *TreeNode) {
if root == nil {
return
}
dfs(root, root.Left)
dfs(root, root.Right)
if s[root.Val] {
if fa != nil && fa.Left == root {
fa.Left = nil
}
if fa != nil && fa.Right == root {
fa.Right = nil
}
if root.Left != nil {
ans = append(ans, root.Left)
}
if root.Right != nil {
ans = append(ans, root.Right)
}
}
}
dfs(fa, root)
return ans
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function delNodes(
root: TreeNode | null,
to_delete: number[],
): Array<TreeNode | null> {
const s: boolean[] = Array(1001).fill(false);
for (const x of to_delete) {
s[x] = true;
}
const ans: Array<TreeNode | null> = [];
const dfs = (root: TreeNode | null): TreeNode | null => {
if (!root) {
return null;
}
root.left = dfs(root.left);
root.right = dfs(root.right);
if (!s[root.val]) {
return root;
}
if (root.left) {
ans.push(root.left);
}
if (root.right) {
ans.push(root.right);
}
return null;
};
if (dfs(root)) {
ans.push(root);
}
return ans;
}