NeetCode #464LC-1110MediumTrees
← Back to All Problems#464 · #1110 · Delete Nodes And Return Forest(删点成林)
📌 Problem Statement & Constraints
Given the root of a binary tree and an array
to_delete of values to remove, delete those nodes and return the roots of the resulting forest. Constraints: the number of nodes is in [1, 1000], 1 <= Node.val <= 1000; values are distinct.💡 Core Algorithmic Approaches
- A node becomes a new forest root when its parent was deleted (or it is the original root) and it is not itself deleted.
- So a DFS carries a flag indicating whether the parent was deleted.
- When a node is deleted, return
Noneso the parent relinks correctly, and recurse into its children withis_root = True. - The deleted node is not added to the result even if
is_rootis true.
💻 Benchmark Python3 Implementation
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
to_del = set(to_delete)
res = []
def dfs(node: Optional[TreeNode], is_root: bool) -> Optional[TreeNode]:
if not node:
return None
deleted = node.val in to_del
if is_root and not deleted:
res.append(node) # a new tree root
# children of a deleted node start their own trees
node.left = dfs(node.left, deleted)
node.right = dfs(node.right, deleted)
return None if deleted else node
dfs(root, True)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(n) for the deletion set plus O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Adding a deleted node to the result: the
not deletedcondition is required. - Passing the parent's deletion status incorrectly:
is_rootfor a child is exactly whether its parent was deleted. - Forgetting to return
Nonefor deleted nodes: the parent would keep pointing at a removed subtree. - Using a list for
to_delete: membership becomes O(k) per node, giving O(n * k); a set makes it O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.