题目描述
思路解析动画文字版
记住三句话：下行扣预算、叶子看剩余、内部看孩子。下面每一帧都在套它。
准备 · 从根出发：开局预算 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题