Problem Description
Given a binary tree root and an integer target, delete all the leaf nodes with value target. Note that once you delete a leaf node with value target, if its parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you cannot).
Key Insights
- A leaf node is defined as a node with no children (both left and right children are null).
- When a leaf node with value equal to the target is deleted, we must check its parent to see if it has become a leaf and also has the target value.
- This can be efficiently solved using a depth-first search (DFS) approach, where we traverse the tree and evaluate each node recursively.
Space and Time Complexity
Time Complexity: O(n), where n is the number of nodes in the tree, as we must potentially visit each node. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack used in depth-first search.
Solution
The problem can be solved using a depth-first search (DFS) algorithm. We will recursively traverse the tree, checking if the current node is a leaf and if it matches the target value. If it does, we remove it by returning null. If not, we continue to traverse its children. After processing both children, we check if the current node has become a leaf and should be deleted. This approach ensures that we handle the cascading deletions required by the problem.