题目描述
思路解析动画文字版
记牢一句:先把左右孩子递归删完,再看自己。只有自己当前是叶子、且值等于 target 才删。删除是自底向上连锁的,下面每一帧都在套这条规则。
总览 · 初始树：先看清这棵树。根是 10,它的左孩子是 20、右孩子是 30。左边那个 20 下面还挂着一个 20;右边的 30 下面挂着一个 20 和一个 40。target 等于 20,所以图里三个值为 20 的节点都是潜在的删除对象,但能不能删要看它当时是不是叶子。
认叶子 · 当前的三个叶子：紫色标出来的是这一刻真正的叶子,也就是没有孩子的节点:左枝最底下的 20、右枝下面的 20、还有右枝下面的 40。删除只从叶子开始。中间的 10、20、30 现在都还有孩子,暂时动不了,得等孩子处理完再说。
后序 · 从根出发下行：后序遍历从根 10 出发,但根要不要删,得等它的左右子树全部处理完才知道,所以现在先不判根,顺着左孩子一路往下钻。记住后序的精神:先孩子,后自己。
下行 · 到根的左孩子 20：走到根的左孩子,这个 20。它下面还挂着一个 20,所以它现在不是叶子,还不能判。继续往它的左孩子钻下去,把底层先处理掉。
下行 · 到左枝最底的 20：钻到最底下这个 20。它左右都没有孩子,到头了。这就是一个叶子,可以开始判定它该不该删。
判定 · 左枝底 20 是叶子：判定这个叶子:它确实没有孩子,而且值是 20,正好等于 target。两个条件都满足,该删。下一帧就把它标红删掉。
删除 · 左枝底 20 变红：左枝最底的 20 被删除,标红。在代码里删除不是真的抹掉内存,而是让它的父亲指向它的那根指针被置成空。这个空值会作为递归结果返回给它的父亲,也就是上面那个 20。
回溯 · 左枝 20 的左孩子断开：回到上面这个 20。它刚收到孩子返回的空值,左孩子指针断开了。而它的右孩子本来就是空的。于是现在它左右都没有孩子了,情况发生了变化。
判定 · 左枝 20 变成新叶子：关键的一刻来了。这个 20 原本不是叶子,可它的左孩子被删后,它现在左右都空,自己升级成了新叶子。再看它的值,正好也是 20,等于 target。新叶子又命中目标值,按规则它也得删。
级联删除 · 左枝 20 也被删：左枝这个 20 被删除,标红。这就是题目说的连锁删除:先删掉底层那个 20,它的父亲因此变成新叶子,而新叶子的值还是 20,于是父亲也跟着被删。一趟后序遍历里,这种连锁是顺着回溯自动发生的。它再向上返回一个空。
回溯 · 根的左孩子断开：回到根 10。它的左孩子返回了空,于是根的左孩子指针也断开了,整条左枝就剩两个红色的已删节点。根自己先别急着判,它还有右子树没处理。现在转向右边的 30。
下行 · 到根的右孩子 30：走到根的右孩子,这个 30。它下面挂着一个 20 和一个 40,有孩子,不是叶子,先不判。按后序规矩,继续往它的左孩子钻。
下行 · 到右枝下的 20：钻到 30 的左孩子,这个 20。它左右都没有孩子,又是一个叶子,可以判了。
判定 · 右枝 20 是叶子：判定这个叶子:没有孩子,值是 20,等于 target,两个条件都满足,该删。
删除 · 右枝 20 变红：30 的左孩子这个 20 被删除,标红,向 30 返回空。注意这次和左边不一样:30 的右边还有别的孩子,所以 30 不一定会变成叶子,等右孩子处理完再看。
下行 · 到右枝下的 40：回到 30,处理它的右孩子,这个 40。它左右都没有孩子,是个叶子,开始判定。
保留 · 40 不等于 target：判定这个 40:它确实是叶子,可是它的值是 40,不等于 target 20。规则要求值等于 target 才删,所以它保留,标绿。它向 30 返回的是它自己,不是空。
判定 · 30 不是叶子,保留：回到 30 做后序判定。它的左孩子被删后是空的,但右孩子 40 保留了下来,所以 30 此刻仍然有孩子,它根本不是叶子。不是叶子就不删,哪怕值碰巧等于 target 也不删,因为删除只针对叶子。30 保留,标绿,向根返回它自己。
判定 · 根 10 不是叶子,保留：最后回到根 10 做后序判定。它的左子树整条被删光了,左孩子是空的,但右孩子 30 保留着,所以根仍然有孩子,不是叶子,保留。再说根的值是 10 也不等于 target。根标绿,整棵树处理完毕。
完成 · 最终结果：收工。绿色的是保留下来的节点:根 10、它的右孩子 30、以及 30 的右孩子 40。红色的三个 20 全被删掉了。按层序写出来,结果就是 [10,null,30,null,40],根的左孩子位置是空。
回放 · 连锁删除链：再回放一下最精彩的连锁:左枝最底的 20 先作为叶子被删,它的父亲那个 20 因此失去全部孩子、升级成新叶子,新叶子值还是 20,于是它也被删。这条自底向上的连锁,正是这道题区别于普通叶子删除的核心,而后序遍历天然就把这件事一次办妥。
边界先想清:单节点只看自己是不是叶子加值;一条全是 target 的小树会从下往上连锁删光,最后可能返回空树。
面试重点:连锁靠后序回溯天然完成一趟即可、删除等价于把父指针置空、自顶向下 BFS 行不通因为删除自底向上传播。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass 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复杂度
- 时间：O(n)，n 是节点数。后序遍历每个节点只访问一次,每次只做常数次比较和指针赋值。连锁删除不会重复访问,因为它顺着同一趟回溯自然完成
- 空间：O(h)，只用递归栈,没有额外容器。栈的峰值深度等于树高 h:链状树最坏 O(n),平衡时 O(log n)。按峰值算空间就是 O(h)
易错点
面试追问把动画讲成自己的话
追问为什么连锁删除一趟后序遍历就能处理完,不用反复扫几遍?
追问删除一个节点在代码里到底做了什么?是真的释放内存吗?
追问能不能用层序遍历也就是 BFS 来做?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分裂二叉树的最大乘积
LeetCode 1339 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题