题目描述
思路解析
一句话答案：LeetCode 1325 删除给定值的叶子节点：后序递归先把左右孩子删完再看自己，删掉叶子后父亲可能变新叶子接着连锁删，一趟后序回溯里天然搞定，时间 O(n)、空间 O(h)。
给一棵树和 target，要删掉哪些叶子
给你二叉树 root 和整数 target，把所有值等于 target 的叶子节点删掉。叶子，就是左右都没有孩子的节点。麻烦在删除会传染：删掉一个叶子后，它的父亲可能因为没了孩子变成新叶子，若新叶子值也等于 target 就接着删，直到删不动。题面例子 root=[10,20,30,20,null,20,40]、target=20。
见到值等于 target 就删，会把树删坏
见值等于 target 的节点就删，树很快散架：还挂着孩子的中间节点被删，它底下整棵子树就断链，答案就错了。所以『值等于 target』只是一半条件，另一半是它此刻必须是叶子，只有摘掉叶子才不牵连别人。剩下的问题就一个：判定一个节点时，怎么保证它的孩子已经删干净？
父亲删不删，得等孩子先删完
一个节点会不会变成叶子，取决于它的孩子删光了没有。所以判它之前得先把左右孩子处理完：递归扎进左右子树清干净，最后才回头轮到自己——先孩子、后父亲，这就是后序。等递归从孩子回来时，左右都空了、值又等于 target，这一刻它才是该删的叶子；只要还留着一个孩子，它就不是叶子，值撞上 target 也不动它。倒过来用前序先判父亲，孩子还没删，连锁的新叶子就漏了。
每个节点递归里做三步、返回一个结果
递归函数 removeLeafNodes(root, target) 分三步。边界：节点为空返回空。接着把左右孩子交给递归，注意把返回值接回去——root.left = removeLeafNodes(root.left, target)、root.right 同理，孩子被删时返回的空就接到 root.left 上。最后判自己：root.left 和 root.right 都空、且 root.val 等于 target，返回空把自己删掉，否则返回 root。
拿题面这棵树，从底下的叶子删起
根 10 左孩子 20、右孩子 30；左边的 20 底下还挂着一个 20；右边的 30 底下挂着 20 和 40。后序从 10 先钻左子树：左孩子 20 还有孩子先放着，到最底下的 20，左右皆空、值 20，命中删掉。
回到父亲 20，左孩子刚被置空、右孩子本就空，值又是 20，自己也成叶子被删——这就是连锁，底下删完正好轮到它。左枝向根返回空。右子树：30 的左孩子 20 是叶子且等于 20，删；右孩子 40 是叶子但 40 不等于 20，保留。回到 30 还留着 40、根 10 还留着 30，都不是叶子，保留。结果 [10,null,30,null,40]，正是题面输出。
接回返回值这步漏了，连锁就断了
最隐蔽的坑是递归后忘了把返回值接回孩子指针，只写 removeLeafNodes(root.left, target) 不赋回 root.left。孩子删了但父亲指针还指着它，连锁就断了。复杂度上后序每个节点访问一次，时间 O(n)；递归栈深度是树高 h，最坏 O(n)、平衡 O(log n)，空间 O(h)。[20,20,20]、target=20 会从底下一路连锁删到根，返回空树。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:先把左右孩子递归删完,再看自己。只有自己当前是叶子、且值等于 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题