Leetcode 1110. Delete Nodes And Return Forest

Problem Explanation

Given a binary tree and a list of nodes to delete, we are required to remove these nodes from the tree. Since deleting a node in a binary tree will result in breaking the tree into a forest of trees (multiple trees), we need to return the roots of all these resulting trees. We need to ensure that we delete the nodes and record the new roots correctly.

Example Walkthrough

Let's take an example: Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] In this case, we are given a binary tree with root node as 1 and we have to delete nodes with values 3 and 5. After deleting the nodes 3 and 5, the binary tree breaks down into a forest of 3 trees with roots [1,6,7]. Hence, the output is [[1,2,null,4],[6],[7]].

Solution Approach

We will use Depth-First Search (DFS) for our solution. We will pass each node of the tree to the DFS recursively, and check if the current node needs to be deleted. If Yes, we set the current node as null and add its non-null children to the output list since those would become new roots. If No, we recursively set its left and right child. The key idea is if a node is deleted, its left and right children would become new roots if they are not null.

This process is repeated until we have traversed all the nodes in the tree.

Java Solution

1
2java
3class Solution {
4  public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
5        List<TreeNode> remaining = new ArrayList<>();
6        Set<Integer> toDeleteSet = new HashSet<>();
7        for (int i : to_delete) {
8            toDeleteSet.add(i);
9        }
10        removeNodes(root, toDeleteSet, remaining);
11        if (!toDeleteSet.contains(root.val)) {
12            remaining.add(root);
13        }
14        return remaining;
15    }
16
17    private TreeNode removeNodes(TreeNode root, Set<Integer> toDeleteSet, List<TreeNode> remaining) {
18        if (root == null) return null;
19        root.left = removeNodes(root.left, toDeleteSet, remaining);
20        root.right = removeNodes(root.right, toDeleteSet, remaining);
21        if (toDeleteSet.contains(root.val)) {
22            if (root.left != null) {
23                remaining.add(root.left);
24            }
25            if (root.right != null) {
26                remaining.add(root.right);
27            }
28            return null;
29        }
30        return root;
31    }
32}

In the above Java solution, for each node, we recursively delete its left child node and right child node. After that, we decide whether to delete this node. If this node needs to be deleted, then add its non-null children to remaining trees to form the new roots. At the end of the function, return root if it is not deleted, else return null.

Python Solution

Let's implement the Java solution logic in Python as well. Python's approach is straightforward and follows the similar DFS idea as explained earlier.

1
2python
3class Solution:
4    def delNodes(self, root, to_delete):
5        to_delete_set = set(to_delete)
6        res = []
7        def helper(root, is_root):
8            if root is None:
9                return None
10            root_deleted = root.val in to_delete_set
11            if is_root and not root_deleted:
12                res.append(root)
13            root.left = helper(root.left, root_deleted)
14            root.right = helper(root.right, root_deleted)
15            return None if root_deleted else root
16        helper(root, True)
17        return res

In the Python solution, we use a helper function to perform DFS on each node. If a node needs to be deleted, its left and right children (if they are not null) are added to the resulting forest and the Node itself is set to None. If the node does not need to be deleted, we continue DFS for its children nodes. At the end of helper function, we return None if the node needs to be deleted else we return the node itself.### JavaScript Solution

Let's also provide a solution for this problem in JavaScript. The approach in JavaScript will also be based on DFS, which would be pretty similar to the approach we considered for Java and Python.

1
2javascript
3class TreeNode {
4    constructor(val, left = null, right = null) {
5        this.val = val;
6        this.left = left;
7        this.right = right
8    }
9}
10
11class Solution {
12    delNodes(root, to_delete) {
13        const toDeleteSet = new Set(to_delete);
14        const res = [];
15        const helper = (root, isRoot) => {
16            if(root === null) return null;
17            const rootDeleted = toDeleteSet.has(root.val);
18            if(!rootDeleted && isRoot) res.push(root);
19            root.left = helper(root.left, rootDeleted);
20            root.right = helper(root.right, rootDeleted);
21            return rootDeleted ? null : root;
22        }
23        helper(root, true);
24        return res;
25    }
26}

In this JavaScript solution, a new class TreeNode is defined for tree nodes, with val, left, and right attributes for the node value and left and right children respectively. A DFS helper function is defined within the delNodes function, and it works similarly to the helper functions in the Python and Java solutions: it looks for nodes to delete, adds any non-null children of deleted nodes to the resulting forest, and sets deleted nodes to null.

It's important to remember that JavaScript uses the Set constructor to create a set of nodes to delete, and the has method to check if a node is in the set, whereas Python uses the set function and the in keyword, and Java uses the HashSet class and the contains method. Despite these differences in syntax, the general approach across all three languages remains the same.