Delete Leaves With a Given Value
The key idea
A node can only be deleted after its children are handled, so process the tree bottom-up. Delete a node's subtrees first; if that leaves the node itself as a leaf whose value equals
target, delete it too. Post-order recursion makes each parent see the freshly pruned version of its children.Problem
You are given the root of a binary tree and an integer target. Delete all the leaf nodes whose value equals target.
Note that once you delete a leaf node, its parent may become a new leaf. If that new leaf also has value target, it must be deleted as well. You keep doing this until no remaining leaf has value target. Return the root of the resulting tree, which may be null if every node is removed.
A leaf is a node with no children — both its left and right are null.
Constraints
- The number of nodes in the tree is in the range
[1, 3000]. 1 <= Node.val, target <= 1000
Examples
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Input: root = [1,3,3,3,2], target = 3
Output: [1,3,null,null,2]
Input: root = [1,2,null,2,null,2], target = 2
Output: [1]
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY