[Leetcode] Problem 1110 - Delete Nodes And Return Forest

Posted on | In ,

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

009q6s.png

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    List<TreeNode> forest = new ArrayList<>();
    Set<Integer> nodes = new HashSet<>();

    for (int node : to_delete) 
        nodes.add(node);
    
    TreeNode newRoot = delete(forest, root, nodes);

    if (newRoot != null)
        forest.add(newRoot);

    return forest;
}

private TreeNode delete(List<TreeNode> forest, TreeNode root, Set<Integer> nodes) {
    if (root == null)
        return null;

    root.left = delete(forest, root.left, nodes);
    root.right = delete(forest, root.right, nodes);

    if (!nodes.contains(root.val))
        return root;

    if (root.left != null)
        forest.add(root.left);
    if (root.right != null)
        forest.add(root.right);

    return null;
}