题目描述
思路解析
一句话答案：LeetCode 1080 根到叶路径上的不足节点：自顶向下把 limit 一路减去节点值往下传，叶子看剩余够不够、内部节点等左右都删光就删自己，一趟后序递归剪枝，时间 O(n)。
哪些节点该从树上删掉
给二叉树 root 和整数 limit。定义：穿过某个节点的每条根到叶路径，节点值之和都＜limit，这节点就算不足、要删掉；叶子指没有孩子的节点。题面例子 root=[40,30,25,50,-10,20,15]、limit=100，四条根到叶路径只有 40→30→50 和 120 够到 100，另外三条都不足。
为什么不能对着每个节点单独算
一个节点是否不足，取决于穿过它的所有根到叶路径。若对每个节点都单独把下面的路径算一遍，同一段路会被反复重算，n 个节点退化成 O(n²)。何况删除会连锁：删掉叶子后父亲可能变成新叶子、要不要删得重判，静态扫一次接不住。
把路径和翻成一路减下去的预算
与其反复求整条路的和，不如给每条路发一份预算 limit：从根往叶子走，每过一个节点就把预算减掉它的值。到叶子时预算还＞0，就说明这条路没凑够 limit、不足。于是「路径和＜limit」等价于「到叶子剩余预算＞0」。
内部节点看的是另一件事：只有它的每条根到叶路径都不足它才不足，这恰好等价于它的左右孩子最后全被删光。道理在于，穿过它的路无非是穿过左、右孩子的路，两个孩子都被删光，那两边的路就全不足，它自然也全不足。而要判孩子删没删光，得先把左右子树处理完再回头定它，先子后父的次序正是后序遍历。
递归返回时，一棵子树要么留要么整删
写成递归，返回值设成「处理后的子树根」：返回节点表示子树留下，返回空表示整棵删掉。到一个节点，先做 limit 减去它的值往下传。叶子若预算还＞0 就返回空、删掉自己，否则返回自己。内部节点先递归处理左右孩子，把新子树接回原位；两边回来后，左右都空就返回空、连自己一起删，还留一个就返回自己。
这里的「删」不是真摘节点，而是让父亲的孩子指针指向空：上层把返回值往左右孩子一接就落定。
拿题面这棵树、limit=100 手推一遍剪枝
根 40，预算 100−40=60，传给两个孩子。左孩子 30，预算 60−30=30；左叶子 50，预算 30−50=−20，−20 不＞0，保留 50；右叶子 −10，预算 30−(−10)=40，40＞0，删掉 −10——扣的是负数，预算不减反增。回到 30，左边还留着 50，30 保留。
右孩子 25，预算 60−25=35；左叶子 20，预算 35−20=15，15＞0，删；右叶子 15，预算 35−15=20，20＞0，删。回到 25，左右孩子都删光，25 自己也删。回到根 40，左边 30 还在，40 保留。删完只剩 40→30→50，正是题面给的那一支。
叶子那个＞写成≥，边界就删错
每个节点递归里只访问一次，做常数次加减比较，时间 O(n)；额外开销是递归栈，层数跟着树高走：树越均衡栈越浅、接近 O(log n)，退化成一条链时栈最深、到 O(n)。
叶子判删只能用剩余预算＞0，写成≥0 就错：路径和正好等于 limit 时剩余预算为 0，这条路够、会被误删。内部节点也别看自身值够不够 limit，删不删只看左右孩子是否都删光。整棵树全不足时连根一起删、返回空树；单节点的树按它自己那条路判。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三句话：下行扣预算、叶子看剩余、内部看孩子。下面每一帧都在套它。
准备 · 从根出发：开局预算 limit = 100。DFS 从根 40 出发，沿每条路往下扣预算，到叶子再结算够不够。把根先标紫，正式下探。
下行 · 节点 40：经过节点 40，预算 100 扣掉 40 剩 60，把这 60 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
下行 · 节点 30：经过节点 30，预算 60 扣掉 30 剩 30，把这 30 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
下行 · 叶子 50：走到叶子 50（紫色）。预算 30 扣掉它的值 50，剩 -20。到叶子了，该结算这条路够不够。
结算 · 留 50：这条根到叶路径和 = 40+30+50 = 120，120 ≥ limit 100，够了。预算已扣到 -20 ≤ 0 也是同一个意思。叶子 50 达标，保留（变绿）。
下行 · 叶子 -10：走到叶子 -10（紫色）。预算 30 扣掉它的值 -10，剩 40。注意它是负数，扣负数等于预算不减反增。到叶子了，该结算这条路够不够。
结算 · 删 -10：这条根到叶路径和 = 40+30+(-10) = 60，60 < limit 100，没够。等价地看，预算还剩 40 > 0 也说明没凑够。叶子 -10 不足，剪掉（变红）。
回收 · 留 30：回到节点 30。它至少还留着一个孩子（左边 50），说明还有一条达标的路穿过它，保留（变绿）。
下行 · 节点 25：经过节点 25，预算 60 扣掉 25 剩 35，把这 35 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
下行 · 叶子 20：走到叶子 20（紫色）。预算 35 扣掉它的值 20，剩 15。到叶子了，该结算这条路够不够。
结算 · 删 20：这条根到叶路径和 = 40+25+20 = 85，85 < limit 100，没够。等价地看，预算还剩 15 > 0 也说明没凑够。叶子 20 不足，剪掉（变红）。
下行 · 叶子 15：走到叶子 15（紫色）。预算 35 扣掉它的值 15，剩 20。到叶子了，该结算这条路够不够。
结算 · 删 15：这条根到叶路径和 = 40+25+15 = 80，80 < limit 100，没够。等价地看，预算还剩 20 > 0 也说明没凑够。叶子 15 不足，剪掉（变红）。
回收 · 删 25：回到节点 25。它的左右孩子刚才全被剪光了，意味着穿过它的每一条根到叶路径都不足，它就是不足节点，自己也剪掉（变红）。这一步是后序的关键：得等孩子定了才能定它。
回收 · 留 40：回到节点 40。它至少还留着一个孩子（左边 30），说明还有一条达标的路穿过它，保留（变绿）。
完成 · 删后的树：处理完毕。最终只剩 40 → 30 → 50 这一支：它的路径和 120 够到了 100。其余不足节点 -10、20、15、25 全被删光。下面我们逐条回放四条路径核对一遍。
回放 · 达标的路：第一条 40 → 30 → 50，和 = 40+30+50 = 120，120 ≥ 100，达标。正因为有它，40 和 30 才得以保留。
回放 · 不足的路：第二条 40 → 30 → (-10)，和 = 60，60 < 100，不足，叶子 -10 被删。它没拖垮 30，因为 30 还有 50 那条达标的路。
回放 · 不足的路：第三条 40 → 25 → 20，和 = 85，85 < 100，不足，叶子 20 被删。
回放 · 不足的路：第四条 40 → 25 → 15，和 = 80，80 < 100，不足，叶子 15 被删。25 的两条路都没够，所以 25 整片连根删掉。
边界先想清：单节点按它自己一条路判；全不足时根也会被删，返回空树。
面试重点：讲清后序的必要性，和「返回新子树根」原地剪枝的写法。
参考代码
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 sufficientSubset( self, root: Optional[TreeNode], limit: int ) -> Optional[TreeNode]: if root is None: return None limit -= root.val if root.left is None and root.right is None: return None if limit > 0 else root root.left = self.sufficientSubset(root.left, limit) root.right = self.sufficientSubset(root.right, limit) return None if root.left is None and root.right is None else root复杂度
- 时间：O(n)，每个节点只在 DFS 里访问一次，常数次加减与比较
- 空间：O(h)，只有递归栈，深度等于树高 h，最坏(退化成链)O(n)，平衡时 O(log n)
易错点
面试追问把动画讲成自己的话
追问为什么必须用后序(自底向上)，不能边下行边删？
追问这道题和「路径总和」那类题什么关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树寻路
LeetCode 1104 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题