今天来聊 LeetCode 1325 这道题删除给定值的叶子节点。一句话说清楚题目给一棵二叉树和一个整数 target你反复删除值为 target 的叶子节点直到整棵树里不存在这种叶子然后返回新的根节点。这题在 LeetCode 上被归为简单题但每次面试问到二叉树递归它都能精准地挖出你对“后序遍历”和“递归返回值”的理解程度。标题里的“耗时100”我理解为一个经验感受只要选对思路提交耗时可以非常短一次遍历解决问题刷出 100% 击败的截图也不难。适合正在刷 LeetCode 热门 100 题、想系统补二叉树递归的新手也适合准备面试想快速过一遍经典题型的同学。下面我把这题从题意、思路、代码到坑点完整拆一遍。1. 题目到底在问什么1.1 一句话拆解题目LeetCode 1325 的题目名是 Remove Nodes From Binary Tree难点不是“删除叶子”这个动作而是题目里强调的repeatedly反复删除。一棵树的叶子不是一成不变的你删掉一层叶子之后原本不是叶子的节点可能变成叶子需要继续判断继续删直到整棵树里再也没有符合条件的叶子为止。输入是一棵普通二叉树节点值不唯一target 可以出现在任意层也没有排序之类的特殊性质。输出是删除完成后仍然连通的根节点如果整棵树被删空返回 null。题目给的是已经定义好的 TreeNode 结构不是数组所以本地测试时得自己根据数组建树再对比结果。这个“从数组到树”的转换过程经常被新手忽略实际调试时非常关键。1.2 三个容易踩空的边界条件第一个边界条件是空树。root 为 null 时直接返回 null这点绝大多数人不会忘但函数入口处一定要写。第二个边界条件是根节点也可能被删空。比如整棵树所有节点值都等于 target那么删到最后一层时根节点会变成叶子根也要删最后函数返回 null。很多第一次做这题的人会默认根节点不可能被删结果答案全错。第三个边界条件是 target 可以是任意整数包括负数、0。判断条件只是在当前节点值等于 target 时触发删除没有额外的大小关系或优先级。这三个边界条件对应到代码里就是三个 base case空节点返回 null叶子且值匹配返回 null叶子但值不匹配返回当前节点。区别只是一次 if。1.3 为什么值得反复刷这题不是难题但浓缩了三个高频考点。第一是递归要能自底向上传播删除结果属于后序遍历的经典应用第二是递归函数的返回值设计这题必须返回 TreeNode把“子节点被删了”这件事告诉父节点返回值设计错了整题就崩第三是对叶子动态定义的理解。完全理解这题之后再去看 LeetCode 814 二叉树剪枝、LeetCode 450 删除二叉搜索树中的节点会发现它们都是同一套“递归返回新子树根父节点承接返回值”的模式。这也是刷题指南里反复强调的把一类题吃透比盲目刷数量有效得多。2. 核心思路选型为什么首选后序遍历2.1 删除逻辑是“自底向上”的删除叶子最直白的理解方式是“剥洋葱”。先把最外层的叶子处理掉处理完之后里面那一层变外露了如果它们值也等于 target再继续处理直到洋葱芯里没有任何可删的叶子为止。计算机里对应的遍历顺序就是后序遍历先访问左孩子再访问右孩子最后访问自己。删除叶子这个操作天然要求你比父节点更早知道自己会被删除这样父节点才能判断“我是不是也变成叶子了”。如果改用前序遍历或者中序遍历问题就很大。前序遍历访问父节点的时候父节点通常还不是叶子你不会删它等它的子节点被删掉之后父节点已经变成叶子了但前序遍历不会再回头处理它于是漏删。这种漏删不是边界情况而是逻辑上的必然所以这个题只要用前序遍历无论怎么补判断都救不回来。2.2 递归函数必须返回 TreeNode 而不是 void这是整道题最重要的设计决策。很多人第一反应是写一个 void 递归在递归里判断到叶子就执行root null但实际上这样写完全不会生效。原因在于 Java 和 Python 里把参数赋值为 null 只是把局部变量指向空并不会影响调用方持有的引用。父节点的root.left还是指向那块内存节点并没有被摘掉。正确的做法是让每个递归调用都返回“处理完后的新子树根”可能是原来的节点也可能是 null然后调用方用root.left removeLeafNodes(root.left, target)接住返回值。这个返回值语义本身就是“更新后的树结构”把删除动作通过赋值传递回上层。这是这题区别与普通遍历题的核心考点也是为什么它适合面试。2.3 迭代解法作为思维拓展递归虽然好写但面试官有时会追问“如果树特别深递归栈溢出怎么办”。这时候需要知道迭代实现我用过两种。第一种是用栈模拟后序遍历每次从栈里弹出一个三元组(node, parent, direction)direction 记录这个节点是父节点的左孩子还是右孩子。访问到一个叶子且值等于 target 时通过 parent 和 direction 把父节点的 left 或 right 置空然后继续处理。这个思路不算复杂但细节很多因为栈里保存的节点状态和父节点引用容易维护出错。第二种是拓扑排序的思路。先统计每个节点的孩子数把初始的所有叶子丢进队列出队时如果值等于 target就把它删除并让父节点的孩子数减一父节点孩子数减到 0 就继续入队。这个做法非常贴合“反复删除”但需要额外的 Map 记录父子关系和孩子数量代码量明显更大。在刷题阶段我建议直接掌握递归版本就够用了。递归的空间复杂度是 O(h)平衡树情况下只有 log n面试时可以接受。只有遇到明确说明树退化成链表且深度极大的场景再考虑把后序遍历改成栈模拟版本。2.4 复杂度分析与“耗时100”的底层依据时间复杂度是 O(n)每个节点最多被访问一次空间复杂度是 O(h)h 是树高最坏情况树退化成链时是 O(n)。这个复杂度已经是最优下界因为至少要遍历整棵树才能知道叶子状态和节点值。这题没有高精度数值没有复杂剪枝也没有额外排序需求所以提交耗时的差距几乎只来自语言和服务器负载。Java 通常 0-2msPython 通常在 20-60ms 这个区间只要你不做多余的遍历不创建无关容器基本都能进入击败率第一梯队。这正是标题里“耗时100”的真实来源思路选对耗时就低得稳定不需要任何花哨优化也不需要反复重提交刷新概率。3. 完整题解实现与关键细节3.1 直接能过的递归代码我给了 Python 和 Java 两个版本都是 LeetCode 上可以直接提交的标准写法。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 rootclass Solution { public TreeNode removeLeafNodes(TreeNode root, int target) { if (root null) { return null; } root.left removeLeafNodes(root.left, target); root.right removeLeafNodes(root.right, target); if (root.left null root.right null root.val target) { return null; } return root; } }两份代码核心就 10 行左右没有任何额外数据结构。很多人觉得代码这么短考不出深度但实际上每一行的位置都是有讲究的尤其是“先递归左右子树再判断叶子”这个顺序不能乱。3.2 代码逐行拆解返回值的语义第一行判空是 base case空子树表示“这个分支不存在返回 null”。接着处理左子树用root.left接住返回值。这里返回的可能是原来那个节点也可能是 null。如果是 null就相当于把左孩子从父节点上摘除。右子树同理。等左右子树都处理完当前节点已经拿到最新的左右孩子状态这时候才判断它是不是叶子。判断条件必须同时满足三个左孩子为 null、右孩子为 null、值等于 target。如果满足返回 null表示当前节点被删除如果不满足返回当前节点本身。需要特别提醒的是不能把判断叶子的代码提前到递归之前。提前的话你删除的只是“初始叶子”等父节点本身变成新叶子后没有机会再被检查结果必然是漏删。这个顺序不是代码风格问题而是算法正确性的核心。3.3 用示例完整走一遍递归调用栈拿 LeetCode 原题的示例一root [1,2,3,2,null,2,4]target 2。从根节点 1 进入先处理左子树。节点 2 是叶子且值为 2返回 null于是节点 1 的左指针变成 null。再处理节点 1 的右子树也就是节点 3。节点 3 先处理自己的左孩子节点 2这个节点是叶子且值为 2返回 null。节点 3 的右孩子是节点 4值为 4叶子但值不等于 target原样返回节点 4。此时节点 3 的左指针指向 null、右指针指向节点 4节点 3 本身不是叶子因此原样返回。回到根节点 1左子树已经是 null右子树是节点 3根节点不是叶子所以返回节点 1。最终结果是 [1, null, 3, null, 4]和题目输出完全一致。再走一个极端例子root [1,1,1]target 1。左孩子是叶子且值为 1返回 null右孩子同理返回 null根节点 1 的左右都变成 null自己也是叶子且值为 1于是返回 null。整棵树被删空。这个例子能直接测试递归会不会漏删根节点本地自测时建议优先跑一遍。3.4 关于提交耗时的实测心态LeetCode 页面上的“耗时 X ms”“击败 Y%”很容易让人执着尤其是看到自己代码击败率从 90% 掉到 80% 时会忍不住反复提交。我的建议是这种简单题没有必要追求极致耗时因为耗时的波动主要来自服务器随机负载同一份代码存在 1ms 以内的抖动非常正常。你真正要盯住的是是否一次 AC、是否覆盖了所有边界样例、能不能在面试时把自己的思路讲清楚。如果非要体验一次“耗时100”的爽感那就先把本地测试用例写全比如空树、单节点匹配、单节点不匹配、整树删除完、链式树等情况确认全部通过后再提交。稳定的 AC 率比页面上的耗时数字有意义得多。4. 易错点与调试实录4.1 误区一前序遍历导致漏删这是新手最常踩的坑。错误写法是进入函数后先判断当前节点是不是叶子、值是不是 target如果是就删除然后再递归左右子树。表面看逻辑很顺实际跑样例就会挂。用 [2,2,2] 这个反例最直观。根节点 2 最开始不是叶子所以第一判断不触发然后递归左孩子左孩子是叶子且值为 2被删掉再递归右孩子右孩子也删掉。递归结束后根节点 2 的左右都变成 null它自己变成叶子且值等于 2应该被删除但前序遍历的过程已经过去不会再回头处理根节点最终错误地返回根节点 2。后序遍历能避免这个问题的原因是每个节点的叶子状态判断都被推迟到左右子树处理完毕之后父节点总是在“已经知道孩子最新状态”的前提下做决定永远不会漏。4.2 误区二父节点变叶子后没人管还有一种错误版本是每个节点内部调用了递归但递归函数声明成 void。问题在于父子之间的信息传递被切断了。你即使在递归函数里写了root null也只是改变函数内部的局部引用对于调用方完全没有影响。严格来说这不是“父节点变叶子后没人管”而是“你根本没有把处理结果同步给上层”。正确做法就是 3.1 里的写法每个递归都返回 TreeNode调用方用root.left ...、root.right ...接收。这样删除信息就会沿着递归栈一层层传上去父节点能感知到子节点是否被删空。4.3 误区三递归出口和空指针处理不严谨第三个常见错误是判空位置放错。比如把空节点判断放在左右递归之后那么当 root 为 null 时还没进入递归就会访问root.left崩溃。还有一种情况是把删除条件写成root.val target但忘了先判断root.left null root.right null结果把所有值等于 target 的节点全删了不管它是不是叶子。这样树的结构直接损坏样例基本秒挂。另外一定要理解不要把删除写成root null而要写成return null。前者只是修改局部参数后者才会作为返回值被上层用赋值操作接收。这两者的区别是这个题目里最容易忽略却又最核心的坑。4.4 本地调试样例的方法LeetCode 默认用数组表示树比如 [1,2,3,2,null,2,4]但本地写测试时不能直接用数组跑 TreeNode需要先写一个按层序构建树的 helper。然后可以加一个简单的前序打印函数来观察结果def preorder(root): if not root: print(null, end ) return print(root.val, end ) preorder(root.left) preorder(root.right)跑样例时把删除前和删除后的序列都打印出来对比变化。如果怀疑递归过程有错也可以在递归函数里临时加一行打印当前节点值和左右子树情况等确认逻辑正确后再删掉。建议测试用例至少覆盖这些场景空树、单节点值等于 target、单节点值不等于 target、整棵树全部等于 target、左右子树对称但 target 分布不对称、树退化成极长链。这些样例跑完基本就能保证提交稳过。5. 常见问题速查与扩展训练5.1 常见问题速查表问题现象根本原因解决方案返回 null 但结果还是原树void 递归或对局部变量置 null让递归函数返回 TreeNode并用 root.left/right 承接根节点删不掉没意识到父节点变叶子后也需删除使用后序遍历最后再判断根节点非叶子节点被删只判断 node.val target漏判叶子条件必须左右子树都为 null 且值等于 target超出递归深度树退化为链递归栈高度过高改栈模拟后序遍历或说明 O(h) 空间可接受空指针异常对空 root 直接访问 left/right函数开头先判空这个表是我本地 debug 时总结的基本覆盖了这题 90% 的提交报错情况。遇到问题先看表比自己瞎调试快很多。5.2 相关变式题一网打尽这题吃透之后建议立刻刷几道变式题巩固“递归返回值 后序”这个模板。LeetCode 814 二叉树剪枝要求删除所有不包含 1 的子树判断条件从“节点值等于 target”变成“子树里是否包含 1”同样要用后序遍历和递归返回值。LeetCode 450 删除二叉搜索树中的节点要处理 BST 的搜索路径和找后继节点但是“递归返回新子树根、父节点承接返回值”的模式完全一致。LeetCode 897 递增顺序搜索树要把所有节点重排成只有右子树的链也是依赖递归返回新根。自己也可以变式删除所有叶子而不管值、删除度为 0 且值等于 target 的节点、只删除一次符合条件的叶子等改的只是判断条件模板不动。这组题放在一起刷两三道之后你会明显感觉到递归返回值这套模式是可以复用的。5.3 面试现场怎么讲这道题如果面试遇到同类题我建议按这个顺序表达。第一句先点出关键“叶子是动态变化的删除行为要自底向上传播所以我会用后序遍历。”第二句说明返回值设计“递归函数返回处理后的新子树根空节点返回 null叶子且值匹配返回 null否则返回当前节点。”第三句直接给例子收尾比如 [2,2,2] 为什么需要完整递归到根。这样表达会让面试官觉得你理解本质而不是背题。如果被追问空间复杂度可以大方承认递归栈是 O(h)在平衡树上是 O(log n)遇到极端链式树可以改用栈模拟后序遍历解决。只要思路清晰这个题在面试里就是送分题。我早期刷这题时其实也先写过一版前序版本[2,2,2] 的样例直接把我打蒙后来才彻底明白“遍历顺序决定删除语义”这个道理。往后遇到所有“删除后父节点可能变化”的二叉树题我都会先画递归调用图、再想返回值代码基本一遍过。最后分享一个小技巧写完先别急着提交把 [2,2,2] target2 和 [1,2,3,2,null,2,4] target2 两个样例在脑内演算一遍确认无漏删再提交。代码短不代表简单这道题值得你多写几次写到能默写不出错你的二叉树递归能力就真正上一个台阶了。
