1110. Delete Nodes And Return Forest

MediumView on LeetCode

Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Post-order DFS. Deleted nodes add non-null children as forest roots. Original root is a root if not deleted.

Algorithm

1to_delete set. DFS returns node or null.
2Recurse on children. If current node deleted: add non-null children to result. Return null.
3If parent is null (root) or parent is deleted: add to result.

Common Pitfalls

•Handle original root as potential forest root. Post-order ensures children handled before parent.

1110.cs

// Approach: Post-order DFS; when deleting a node add its non-null children as new roots; return null upward when a node is deleted.
// Time: O(n) Space: O(n)

public class TreeNode(TreeNode root, int[] to_delete)
    {
        var ans = new List<TreeNode>();
        var set = new HashSet<int>(to_delete);
        DFS(root, set, true, ans);
        return ans;
    }

    private TreeNode DFS(TreeNode root, HashSet<int> set, bool isRoot, List<TreeNode> ans)
    {
        if (root == null)
            return null;

        bool deleted = set.Contains(root.val);
        if (isRoot && !deleted)
            ans.Add(root);

        root.left = DFS(root.left, set, deleted, ans);
        root.right = DFS(root.right, set, deleted, ans);
        return deleted ? null : root;
    }
}

Was this solution helpful?