How do I approach solving 'Delete Leaves With a Given Value'?

The problem can be tackled using DFS traversal, checking each node recursively and deleting leaves that match the target value. Once deleted, check if the parent becomes a leaf and continue deleting if necessary.

What is the time complexity of the 'Delete Leaves With a Given Value' problem?

The time complexity is O(n), where n is the number of nodes in the tree. Each node is visited exactly once during the DFS traversal.

How does recursion work in the solution for this problem?

Recursion helps in traversing the tree and ensuring that after each deletion, the parent node is checked if it becomes a leaf. The process continues until no deletions are left.

Can the tree be empty in the 'Delete Leaves With a Given Value' problem?

Yes, the tree can be empty, in which case the result is also an empty tree.

What if no leaf nodes have the target value in the 'Delete Leaves With a Given Value' problem?

If no leaf nodes match the target value, the tree will remain unchanged and be returned as-is.

#1325

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

删除给定值的叶子节点

给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的叶子节点。注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。也就是说，你需要重复此过程直到不能继续删…

树深度优先搜索二叉树

题目描述

给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。

注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。

也就是说，你需要重复此过程直到不能继续删除。

示例 1：

输入：root = [1,2,3,2,null,2,4], target = 2
输出：[1,null,3,null,4]
解释：
上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。
有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。

示例 2：

输入：root = [1,3,3,3,2], target = 3
输出：[1,3,null,null,2]

示例 3：

输入：root = [1,2,null,2,null,2], target = 2
输出：[1]
解释：每一步都删除一个绿色的叶子节点（值为 2）。

提示：

树中节点数量的范围是 [1, 3000]。
1 <= Node.val, target <= 1000

lightbulb

解题思路

方法一：递归

我们先判断 $root$ 节点是否为空，若为空，则返回空。

否则，递归地处理 $root$ 的左右子树，即调用 root.left = removeLeafNodes(root.left, target) 和 root.right = removeLeafNodes(root.right, target)。

然后判断 $root$ 节点是否为叶子节点，即判断 $root.left$ 和 $root.right$ 是否为空，且 $root.val$ 是否等于 $target$ 。若是，则返回空，否则返回 $root$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# 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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Understanding of DFS and its application in tree-based problems.
question_mark
Ability to manage tree reconstruction and state tracking through recursion.
question_mark
Experience in dealing with binary trees and edge cases like consecutive deletions.

warning

常见陷阱

外企场景

error
Not properly handling the parent-child relationship after deletion, leading to missed deletions.
error
Failing to account for edge cases where multiple deletions affect the tree structure.
error
Incorrectly managing the recursive return values, which can result in incorrect tree reconstruction.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to remove nodes with any value instead of just leaf nodes.
arrow_right_alt
Extend the problem to handle more complex tree structures with additional constraints.
arrow_right_alt
Adjust the problem to return a list of deleted nodes instead of just the modified tree.

help

常见问题

外企场景

继续练习

#1315 祖父节点值为偶数的节点和 #1339 分裂二叉树的最大乘积 #1305 两棵二叉搜索树中的所有元素