Space
Open
From Fieldwork
Scales
Archive
The most elegant way to solve this is using Post-Order Traversal (Bottom-Up).
Set Optimization: Convert to_delete to a set for O(1) lookup time.
Recursion Logic: We define a helper function that returns None if the current node should be deleted (telling the parent to sever the link) or returns the node itself if it should stay.
Identifying New Roots: If a node is marked for deletion, its children (if they exist and haven't been deleted) automatically become the roots of new trees. We add them to our result list immediately before deleting the current node.
Why write it like this?
Single Responsibility: Each call to process(node) has one job: "Clean my subtrees and tell my parent if I still exist."
Implicit Logic: You don't need to pass state (is_root) down. The state is handled naturally by the call stack.
The "Snip" is Automatic: By setting node.left = process(node.left), the parent automatically loses the reference to a deleted child without any if/else logic needed inside the parent's block.
class Solution:
def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:
# 1. Use a set for O(1) lookups
delete_set = set(to_delete)
forest = []
def process(node):
if not node:
return None
# 2. Process children first (Bottom-Up)
# This ensures children are already handled if they needed deleting
node.left = process(node.left)
node.right = process(node.right)
# 3. Handle the current node
if node.val in delete_set:
# If this node is gone, its surviving children are now independent roots
if node.left: forest.append(node.left)
if node.right: forest.append(node.right)
return None # "Delete" this node by returning None to its parent
return node # Keep this node
# 4. Kick off the process and check if the original root survived
if process(root):
forest.append(root)
return forestPractice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode