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

哪些节点该从树上删掉

给二叉树 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，删不删只看左右孩子是否都删光。整棵树全不足时连根一起删、返回空树；单节点的树按它自己那条路判。

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;
    }
}