1325. 删除给定值的叶子节点

Hi 大家好，我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 周赛题解。

这里是第 172 期的第 3 题，也是题目列表中的第 1325 题 -- 『删除给定值的叶子节点』

题目描述

给你一棵以 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）。

示例 4：

输入：root = [1,1,1], target = 1
输出：[]

示例 5：

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

提示：

• 1 <= target <= 1000
• 每一棵树最多有 3000 个节点。
• 每一个节点值的范围是 [1, 1000]。

官方难度

MEDIUM

解决思路

题目给定了一个二叉树和一个目标值 target，我们需要删除所有值为 target 的叶节点。这里需要注意的是，如果某一个节点本身不是叶节点，但是它的叶节点因为值的原因被删除了，那么这时候它便成为了新的叶节点。于是也需要对它的值进行判断和处理。

读完题目后，小猪第一反应是，这又是一道非常套路的题。相信熟悉套路的小伙伴们已经有思路了吧，不过我们这里还是一步一步来。

首先，第一个需要解决的问题是，我们需要判断出符合要求的叶节点。叶节点即为没有任何子节点的节点。由于我们这里是二叉树，并且题目给定的结构中用特定的 null 值来标识空节点，所以我们只需要判断该节点的左右子节点是否为 null 值，然后判断该节点的值是否为目标值 target 即可。例如：

node.left === null && node.right === null && node.val === target

这里可以做一个小小的优化，减少一个判断。因为各个节点的对象都是不一样的，哪怕值一样那个节点也是不同的节点。这时候只有当两个节点都是空值 null 的时候才会值相等，所以我们可以直接判断左右两个子节点是否相等，即可完成左右两个子节点是否都是空值的判断。例如：

node.left === node.right && node.val === target

有了结果的判断逻辑之后，接下来就是如何遍历这个二叉树。根据题目要求，由于子节点的处理结果会影响到父节点的处理过程，所以我们应当先访问左右两个子节点，再访问节点本身。这也就对应着二叉树遍历方式中的后序遍历。即节点遍历顺序为左子节点 -> 右子节点 -> 节点本身。

有了遍历过程，接下来的就是返回值的处理。因为如果当前节点需要被删除，那么方式其实是通过修改父节点对应的指针。而父节点我们无法直接在当前节点访问到。如果重新从根节点开始查找当前节点的父节点，我们还需要额外的遍历开销。所以这里考虑通过递归调用的返回值来做处理。

直接方案

基于上面的思路，我们可以得到如下的递归流程：

1. 如果左子节点存在，递归的处理当前节点的左子节点，并更新左子节点的值。
2. 如果右子节点存在，递归的处理当前节点的右子节点，并更新右子节点的值。
3. 判断当前节点是否是符合要求的叶节点，并返回当前节点的最新值。

可能有的小伙伴会问，这个递归怎么没有终止条件呢？其实这里终止条件隐藏在处理逻辑里了。仔细观察我们的逻辑就会发现，判断左子节点存在和判断右子节点存在，其实就是递归进行下去的终止条件。

基于以上流程，我们可以实现类似下面的代码：

const removeLeafNodes = (node, target) => {
  node.left && (node.left = removeLeafNodes(node.left, target));
  node.right && (node.right = removeLeafNodes(node.right, target));
  return node.left === node.right && node.val === target ? null : node;
};

基于递归来实现看起来的确很简洁。这里我们也可以写成一行代码来实现，不过这一行会比较长一点。例如下面这样：

const removeLeafNodes = (node, target) => (node.left && (node.left = removeLeafNodes(node.left, target)), node.right && (node.right = removeLeafNodes(node.right, target)), node.left === node.right && node.val === target ? null : node);

总结

这是一道非常套路的题，用来考察二叉树的遍历过程。题目并不难，实现的代码也很少。所以上面的内容着重在于前期的思路分析。希望熟悉套路的小伙伴们不要鄙视小猪废话太多啦，也希望借此让不熟悉套路的小伙伴们摸到这个套路的方法。

加油武汉，天佑中华

相关链接

• Weekly Contest 172 题目列表
• 系列题解 repo
• 我的 segmentfault 专栏
• 我的知乎专栏