Leetcode 1325. Delete Leaves With a Given Value

Problem

Leetcode 1325 - Delete Leaves With a Given Value

Example:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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]
Explanation: Leaf nodes in green with value (target = 2) are removed at each step.

Approach

We can use DFS to find the deepest node (leaf) then if that is the target, then we simply remove it by returning None

Here is the Python code for the solution:

class Solution:
    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        def dfs(root):
            if not root:
                return None
            
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            if root.val == target and not root.left and not root.right:
                return None
            return root
        
        return dfs(root)
    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$