NeetCode #463LC-1325MediumTreesNC 250
← Back to All Problems#463 · #1325 · Delete Leaves With a Given Value(删除给定值的叶子节点)
📌 Problem Statement & Constraints
Given the root of a binary tree and an integer
target, repeatedly delete all leaf nodes with value target until no more such leaves exist. Return the root. Constraints: the number of nodes is in [1, 3000], 1 <= Node.val, target <= 1000.💡 Core Algorithmic Approaches
- Process the children first (post-order), so a node that becomes a leaf only after its children are deleted is handled in the same pass.
- After recursing, if the node is now a leaf and its value equals
target, returnNoneto delete it. - Returning the (possibly
None) subtree root lets the parent relink automatically. - A single post-order pass reaches the fixpoint, so no repeated scanning is needed.
💻 Benchmark Python3 Implementation
class Solution:
def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
if not root:
return None
# children first, so newly created leaves are handled in this pass
root.left = self.removeLeafNodes(root.left, target)
root.right = self.removeLeafNodes(root.right, target)
if not root.left and not root.right and root.val == target:
return None # delete this now-leaf node
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Checking for a leaf before recursing: a node whose children will be deleted would not be recognised as a leaf. The check must come after the recursive calls.
- Deleting by value without the leaf check: an internal node with the target value must be kept.
- Repeating passes until stable: a single post-order pass already reaches the fixpoint, because deletions propagate upward.
- Forgetting to assign the recursive results: the deletions would not take effect.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.