Delete Leaves With a Given Value

Problem Id: 1325 Difficulty: Medium Tag: Tree


Intuition

Do a DFS to re-construct the tree. We could return the current node in the DFS method, and set each node's left and right node to the return value of their DFS result.

In this process, if we need to remove it, we could just return None.

Since this should be done recursively, we need to choose post-order as the order of DFS.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
        return self._dfs(root, target)

    def _dfs(self, node, target):
        if node is None:
            return None
        node.left = self._dfs(node.left, target)
        node.right = self._dfs(node.right, target)

        if node.left is None and node.right is None and node.val == target:
            return None
        return node