⚡Flashcard Drill➔
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

  1. 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.
  2. After recursing, if the node is now a leaf and its value equals target, return None to delete it.
  3. Returning the (possibly None) subtree root lets the parent relink automatically.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems