Delete Leaves With a Given Value — LeetCode 1325 Python Solution

The problem

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).

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).

Python solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeLeafNodes(
        self, root: Optional[TreeNode], target: int
    ) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if root.left is None and root.right is None and root.val == target:
            return None
        return root

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1325. Delete Leaves With a Given Value is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems