1110.md

1110. Delete Nodes And Return Forest

Level:

Topic:

Question

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.

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Intuition

Recursive:

How to deal with to_delete?

• store in a global variable hashset for search

When to add the tree to return list?

• when it has no parent and not a deleted node
• no parent means it's the root of a tree

How to remove the node being deleted?

• return back the value to assign node's left and right and if it's the deleted node, return null for assignment

Code

Time: O(n)
Space: O(d+n)

Recursive

List<TreeNode> ans = new ArrayList<>();
HashSet<Integer> set = new HashSet<>();

public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
    for (int d:to_delete)
        set.add(d);

    // the root might be in the to_delete list
    // but all to_delete node's children should have no parent
    // since the to_delete node should be removed from tree
    helper(root, false);

    return ans;
}

private TreeNode helper(TreeNode root, boolean hasParent) {
    // base case, if traversed to the null node, return null and stop traversing
    if (root == null)
        return null;

    // check if current node is in the to_delete list
    boolean deleted = set.contains(root.val);

    // if a node has no parent but not in the delete list
    // it's a disjoint tree root node
    if (!hasParent && !deleted)
        ans.add(root);

    // if it's the node being deleted, that node should be returned null
    // else it should be the original value
    root.left = helper(root.left, !deleted);
    root.right = helper(root.right, !deleted);

    return deleted ? null:root;
}