LeetCode 1080中等树 · BST

根到叶路径上的不足节点图解题解

这道题到底在问什么

给二叉树 root 和整数 limit。若通过某节点的每条根到叶路径，节点值之和全都 < limit，则该节点不足，删除它，返回删完后的树。叶子是没有孩子的节点。

输入: root=[40,30,25,50,-10,20,15], limit=100
输出: 保留 40 → 30 → 50 这一支

最优解：一步一步想明白

3记住三句话：下行扣预算、叶子看剩余、内部看孩子。下面每一帧都在套它。
4预算 limit = 100开局预算 limit = 100。DFS 从根 40 出发，沿每条路往下扣预算，到叶子再结算够不够。把根先标紫，正式下探。
5100 - 40 = 60经过节点 40，预算 100 扣掉 40 剩 60，把这 60 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
660 - 30 = 30经过节点 30，预算 60 扣掉 30 剩 30，把这 30 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
730 - 50 = -20走到叶子 50（紫色）。预算 30 扣掉它的值 50，剩 -20。到叶子了，该结算这条路够不够。
8和 120 ≥ 100 → 留这条根到叶路径和 = 40+30+50 = 120，120 ≥ limit 100，够了。预算已扣到 -20 ≤ 0 也是同一个意思。叶子 50 达标，保留（变绿）。
930 - -10 = 40走到叶子 -10（紫色）。预算 30 扣掉它的值 -10，剩 40。注意它是负数，扣负数等于预算不减反增。到叶子了，该结算这条路够不够。
10和 60 < 100 → 删这条根到叶路径和 = 40+30+(-10) = 60，60 < limit 100，没够。等价地看，预算还剩 40 > 0 也说明没凑够。叶子 -10 不足，剪掉（变红）。
11还有活孩子 → 留 30回到节点 30。它至少还留着一个孩子（左边 50），说明还有一条达标的路穿过它，保留（变绿）。
1260 - 25 = 35经过节点 25，预算 60 扣掉 25 剩 35，把这 35 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
1335 - 20 = 15走到叶子 20（紫色）。预算 35 扣掉它的值 20，剩 15。到叶子了，该结算这条路够不够。
14和 85 < 100 → 删这条根到叶路径和 = 40+25+20 = 85，85 < limit 100，没够。等价地看，预算还剩 15 > 0 也说明没凑够。叶子 20 不足，剪掉（变红）。
1535 - 15 = 20走到叶子 15（紫色）。预算 35 扣掉它的值 15，剩 20。到叶子了，该结算这条路够不够。
16和 80 < 100 → 删这条根到叶路径和 = 40+25+15 = 80，80 < limit 100，没够。等价地看，预算还剩 20 > 0 也说明没凑够。叶子 15 不足，剪掉（变红）。
17左右皆删 → 删 25回到节点 25。它的左右孩子刚才全被剪光了，意味着穿过它的每一条根到叶路径都不足，它就是不足节点，自己也剪掉（变红）。这一步是后序的关键：得等孩子定了才能定它。
18还有活孩子 → 留 40回到节点 40。它至少还留着一个孩子（左边 30），说明还有一条达标的路穿过它，保留（变绿）。
19保留 50,30,40处理完毕。最终只剩 40 → 30 → 50 这一支：它的路径和 120 够到了 100。其余不足节点 -10、20、15、25 全被删光。下面我们逐条回放四条路径核对一遍。
2040+30+50 = 120第一条 40 → 30 → 50，和 = 40+30+50 = 120，120 ≥ 100，达标。正因为有它，40 和 30 才得以保留。
2140+30+(-10) = 60第二条 40 → 30 → (-10)，和 = 60，60 < 100，不足，叶子 -10 被删。它没拖垮 30，因为 30 还有 50 那条达标的路。
2240+25+20 = 85第三条 40 → 25 → 20，和 = 85，85 < 100，不足，叶子 20 被删。
2340+25+15 = 80第四条 40 → 25 → 15，和 = 80，80 < 100，不足，叶子 15 被删。25 的两条路都没够，所以 25 整片连根删掉。

⚠️ 容易写错的地方

✗ 错：叶子用 rem ≥ 0 判删

✓ 对：只有 rem > 0 才删

路径和正好等于 limit(rem=0)算够，要保留，写成 ≥ 会误删边界

✗ 错：自顶向下提前删内部节点

✓ 对：必须后序，等孩子定了再定它

内部节点删不删取决于孩子全删没全删，没处理完孩子无法判断

✗ 错：默认预算一路单调减

✓ 对：节点值可为负，扣负数预算会变大

负节点让剩余预算回升，不能假设越往下预算越小

✗ 错：内部节点看自身值是否够 limit

✓ 对：内部节点只看左右孩子是否都被删

不足的定义是「穿过它的每条路都不足」，等价于两个孩子都被删

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if (!root) {
            return nullptr;
        }
        limit -= root->val;
        if (!root->left && !root->right) {
            return limit > 0 ? nullptr : root;
        }
        root->left = sufficientSubset(root->left, limit);
        root->right = sufficientSubset(root->right, limit);
        return !root->left && !root->right ? nullptr : root;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        limit -= root.val;
        if (root.left == null && root.right == null) {
            return limit > 0 ? null : root;
        }
        root.left = sufficientSubset(root.left, limit);
        root.right = sufficientSubset(root.right, limit);
        return root.left == null && root.right == null ? null : root;
    }
}

复杂度

时间

O(n)

每个节点只在 DFS 里访问一次，常数次加减与比较

空间

O(h)

只有递归栈，深度等于树高 h，最坏(退化成链)O(n)，平衡时 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着根到叶路径上的不足节点的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么必须用后序(自底向上)，不能边下行边删？+

内部节点是否不足，取决于它下面所有根到叶路径是否全部不足，而这要等左右子树都处理完、看孩子是不是都被删了才能知道。所以决定内部节点必须放在递归返回时(后序)。叶子可以在下行到底时直接判，因为它就是一条完整路径的终点。

这道题和「路径总和」那类题什么关系？+

都是 DFS 累计根到叶的路径和。不同点在于这里不是查询有没有某条路，而是要根据每条路够不够，回头把不达标的节点从树上删掉。实现上用「递归返回新的子树根」这个套路原地改树：返回 null 表示这棵子树整个被删。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把根到叶路径上的不足节点一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1080中等树 · BST

根到叶路径上的不足节点图解题解

这道题到底在问什么

输入: root=[40,30,25,50,-10,20,15], limit=100
输出: 保留 40 → 30 → 50 这一支

最优解：一步一步想明白

3记住三句话：下行扣预算、叶子看剩余、内部看孩子。下面每一帧都在套它。
4预算 limit = 100开局预算 limit = 100。DFS 从根 40 出发，沿每条路往下扣预算，到叶子再结算够不够。把根先标紫，正式下探。
5100 - 40 = 60经过节点 40，预算 100 扣掉 40 剩 60，把这 60 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
660 - 30 = 30经过节点 30，预算 60 扣掉 30 剩 30，把这 30 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
730 - 50 = -20走到叶子 50（紫色）。预算 30 扣掉它的值 50，剩 -20。到叶子了，该结算这条路够不够。
8和 120 ≥ 100 → 留这条根到叶路径和 = 40+30+50 = 120，120 ≥ limit 100，够了。预算已扣到 -20 ≤ 0 也是同一个意思。叶子 50 达标，保留（变绿）。
930 - -10 = 40走到叶子 -10（紫色）。预算 30 扣掉它的值 -10，剩 40。注意它是负数，扣负数等于预算不减反增。到叶子了，该结算这条路够不够。
10和 60 < 100 → 删这条根到叶路径和 = 40+30+(-10) = 60，60 < limit 100，没够。等价地看，预算还剩 40 > 0 也说明没凑够。叶子 -10 不足，剪掉（变红）。
11还有活孩子 → 留 30回到节点 30。它至少还留着一个孩子（左边 50），说明还有一条达标的路穿过它，保留（变绿）。
1260 - 25 = 35经过节点 25，预算 60 扣掉 25 剩 35，把这 35 的预算交给它下面的子树去凑。先递归处理它的左右孩子，自己暂不下结论。
1335 - 20 = 15走到叶子 20（紫色）。预算 35 扣掉它的值 20，剩 15。到叶子了，该结算这条路够不够。
14和 85 < 100 → 删这条根到叶路径和 = 40+25+20 = 85，85 < limit 100，没够。等价地看，预算还剩 15 > 0 也说明没凑够。叶子 20 不足，剪掉（变红）。
1535 - 15 = 20走到叶子 15（紫色）。预算 35 扣掉它的值 15，剩 20。到叶子了，该结算这条路够不够。
16和 80 < 100 → 删这条根到叶路径和 = 40+25+15 = 80，80 < limit 100，没够。等价地看，预算还剩 20 > 0 也说明没凑够。叶子 15 不足，剪掉（变红）。
17左右皆删 → 删 25回到节点 25。它的左右孩子刚才全被剪光了，意味着穿过它的每一条根到叶路径都不足，它就是不足节点，自己也剪掉（变红）。这一步是后序的关键：得等孩子定了才能定它。
18还有活孩子 → 留 40回到节点 40。它至少还留着一个孩子（左边 30），说明还有一条达标的路穿过它，保留（变绿）。
19保留 50,30,40处理完毕。最终只剩 40 → 30 → 50 这一支：它的路径和 120 够到了 100。其余不足节点 -10、20、15、25 全被删光。下面我们逐条回放四条路径核对一遍。
2040+30+50 = 120第一条 40 → 30 → 50，和 = 40+30+50 = 120，120 ≥ 100，达标。正因为有它，40 和 30 才得以保留。
2140+30+(-10) = 60第二条 40 → 30 → (-10)，和 = 60，60 < 100，不足，叶子 -10 被删。它没拖垮 30，因为 30 还有 50 那条达标的路。
2240+25+20 = 85第三条 40 → 25 → 20，和 = 85，85 < 100，不足，叶子 20 被删。
2340+25+15 = 80第四条 40 → 25 → 15，和 = 80，80 < 100，不足，叶子 15 被删。25 的两条路都没够，所以 25 整片连根删掉。

⚠️ 容易写错的地方

✗ 错：叶子用 rem ≥ 0 判删

✓ 对：只有 rem > 0 才删

路径和正好等于 limit(rem=0)算够，要保留，写成 ≥ 会误删边界

✗ 错：自顶向下提前删内部节点

✓ 对：必须后序，等孩子定了再定它

内部节点删不删取决于孩子全删没全删，没处理完孩子无法判断

✗ 错：默认预算一路单调减

✓ 对：节点值可为负，扣负数预算会变大

负节点让剩余预算回升，不能假设越往下预算越小

✗ 错：内部节点看自身值是否够 limit

✓ 对：内部节点只看左右孩子是否都被删

不足的定义是「穿过它的每条路都不足」，等价于两个孩子都被删

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        if (!root) {
            return nullptr;
        }
        limit -= root->val;
        if (!root->left && !root->right) {
            return limit > 0 ? nullptr : root;
        }
        root->left = sufficientSubset(root->left, limit);
        root->right = sufficientSubset(root->right, limit);
        return !root->left && !root->right ? nullptr : root;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        limit -= root.val;
        if (root.left == null && root.right == null) {
            return limit > 0 ? null : root;
        }
        root.left = sufficientSubset(root.left, limit);
        root.right = sufficientSubset(root.right, limit);
        return root.left == null && root.right == null ? null : root;
    }
}

复杂度

时间

O(n)

每个节点只在 DFS 里访问一次，常数次加减与比较

空间

O(h)

只有递归栈，深度等于树高 h，最坏(退化成链)O(n)，平衡时 O(log n)

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

为什么必须用后序(自底向上)，不能边下行边删？+

这道题和「路径总和」那类题什么关系？+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

根到叶路径上的不足节点 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

根到叶路径上的不足节点 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

根到叶路径上的不足节点图解题解

根到叶路径上的不足节点图解题解