LeetCode 1080. 根到叶路径上的不足节点

2022-04-14 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1080. 根到叶路径上的不足节点

题意分析

给一棵二叉树和一个阈值 limit。若经过某个节点的每一条根到叶路径，其节点值之和都严格小于 limit，这个节点就是「不足节点」，需要被删除。删除是反复进行的，返回删干净之后的树。

定义里最关键的是「经过它的所有路径」这个全称量词。一个节点只要还有任意一条经过它的路径达到了 limit，它就必须保留；只有当所有路径都不达标时才删。等价的否定形式更好写代码：保留 ⟺ 存在一条经过它的根到叶路径，其和不小于 limit。

「反复删除」听起来需要多轮迭代——删掉一批叶子后，原来的内部节点可能变成新叶子，又要重新判断。但只要换个角度就能一次搞定：一个内部节点被删，当且仅当它的左右子树都被删光；而子树是否删光，只取决于子树内部的路径，与外部无关。于是一趟自底向上的后序遍历就能完成全部删除，不需要循环到不动点。

判断某条路径是否达标，需要知道「从根到当前节点已经累积了多少」。有两种等价的传参方式：向下传「已累积和」，到叶子处与 limit 比较；或者向下传「还差多少」，即 limit - node.val，到叶子处与 0 比较。本题代码采用后者——传剩余额度，叶子处判 node.val < limit 即可，减法在下传时一次完成，读起来更贴近「额度」的语义。

约束是节点数在 [1, 5000]，节点值在 [-10^5, 10^5]，limit 在 [-10^9, 10^9]。节点值可以为负，这意味着路径和不随深度单调增加，不能中途「提前判定这条路已经没救了」而剪枝——必须走到叶子才能结算。递归深度最坏 5000 层，在 Java 与 Go 的默认栈下是安全的。

边界：根节点本身可能被删，此时返回空；叶子节点的判据是 node.val < limit（严格小于才删，等于要保留）；空树直接返回空。

解法：DFS 剪枝

核心思路

直接做法是枚举每条根到叶路径，达标时再沿路径标记所有节点，最后删除未标记节点。树的叶子数虽不超过节点数，但同一段祖先路径会被许多叶子反复处理；若保存或逐条回扫路径，最坏会达到 $O(nh)$，还要维护路径与标记。真正需要的只有一个结论：当前子树是否还存在一条达标路径，它可以在回溯时一次算出。

换成递归：定义 dfs(node, need) 的返回值为「以 node 为根的子树在剪枝之后剩下什么」，返回 null 表示整棵子树都被删光。参数 need 的含义是「从 node 开始还需要凑够的路径和」，也就是原始阈值减去 node 之前所有祖先的值。

三种情形：

node == null：空子树，返回 null。这一支既处理空树输入，也让父层不必逐个判空。

node 是叶子：经过它的路径只有一条，是否达标就看 node.val 能不能补上剩余额度。node.val < need 说明补不上，整条路径不足，删掉自己返回 null；否则保留。

node 是内部节点：先递归处理左右子树，把返回值直接接回 node.left、node.right——这一步同时完成了「删除子节点」的动作。递归时传下去的额度是 need - node.val，因为 node 自己已经贡献了 node.val。递归回来后，若左右都变成 null，说明经过 node 的所有路径都不达标（原本的每条路径都被否决了），node 也要删；否则保留。

不变量：dfs(node, need) 返回非空，当且仅当以 node 为根的子树中存在一条从 node 到某个原始叶子的路径，其节点值之和不小于 need；且返回时该子树内所有不足节点都已被删除。叶子情形直接由比较得出；内部节点情形由「左右子树至少有一支保留」推出，而那一支的保留恰好意味着存在一条达标路径。

这条不变量也解释了为什么一趟后序遍历就够：「反复删除」的传递性已经被递归的回溯顺序天然覆盖了——子树先被处理完，父节点看到的已经是最终状态，不会出现「删完子节点后父节点又该删」的遗留。

用结构归纳即可证明正确性：原始叶子只有一条候选路径，比较后返回值显然正确；假设左右子树的返回值都满足上述语义，那么内部节点在且仅在至少一个孩子非空时保留，也就等价于其子树存在达标路径。由叶子向根归纳，根的返回值就是题目要求的最终树。

解题步骤

参数传「剩余额度」而不是「已累积和」：两者等价，但传额度时叶子判据只需 node.val < need 一次比较，且减法在下传处集中完成，不易写漏。

先写 node == null 返回 null：既覆盖空树，也让内部节点分支可以无脑递归左右孩子而不必判空。

叶子判据用严格小于 node.val < need：路径和小于原始 limit 才算不足，恰好等于阈值时必须保留。把 < 写成 <= 会多删一批节点。

递归结果必须回写到 node.left / node.right：dfs 只返回剪枝后的子树，不回写就等于什么都没删。这是本题最容易漏的一行。

递归时传 need - node.val：把当前节点的贡献从额度里扣掉。注意扣的是 node.val 而不是子节点的值——子节点的值会在它自己那一层比较或继续向下扣。

回溯后再判 left == null && right == null：这个判断必须在两次递归之后，用的是更新过的孩子指针；写在递归之前判的是原始结构，等于没做剪枝。

叶子分支要写在内部节点分支之前：叶子也满足「左右都为空」，若先执行内部节点逻辑，会对叶子递归两个空孩子并直接判定为「左右都空」而删掉，把所有叶子无条件删光。

以 root = [1, 2, 3]、limit = 4 走一遍：根节点先把剩余额度从 4 减为 3。左叶子 2 满足 2 < 3，对应路径和 1 + 2 = 3，被删除；右叶子 3 不满足 3 < 3，对应路径和恰好为 4，必须保留。回到根节点时右孩子仍非空，因此根也保留，最终得到 [1, null, 3]。

再看不能提前剪枝的反例：root = [10, -100, 5]、limit = 5。虽然走到根时累计和 10 已经达标，但左路径最终是 -90，左叶子仍应删除；右路径最终是 15，右叶子保留。负数使路径和没有单调性，结论只能在原始叶子处落定。

代码实现

// 若子树返回空，则当前节点对应子树被剪掉。
class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root, limit);
    }

    private TreeNode dfs(TreeNode node, int need) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            if (node.val < need) {
                return null;
            }
            return node;
        }

        node.left = dfs(node.left, need - node.val);
        node.right = dfs(node.right, need - node.val);

        if (node.left == null && node.right == null) {
            return null;
        }
        return node;
    }
}

// 若子树返回空，则当前节点对应子树被剪掉。
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
	return dfsSufficient(root, limit)
}

func dfsSufficient(node *TreeNode, need int) *TreeNode {
	if node == nil {
		return nil
	}
	if node.Left == nil && node.Right == nil {
		if node.Val < need {
			return nil
		}
		return node
	}

	node.Left = dfsSufficient(node.Left, need-node.Val)
	node.Right = dfsSufficient(node.Right, need-node.Val)

	if node.Left == nil && node.Right == nil {
		return nil
	}
	return node
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为节点数。凭的是每个节点恰好被 dfs 访问一次，函数体内只有常数次比较与指针赋值；「反复删除」不需要多轮迭代，后序回溯天然覆盖了传递效应。

空间复杂度：$O(h)$，其中 h 为树高。算法原地修改指针，不建新树也不保存路径，额外开销只有递归栈；平衡树时为 $O(\log n)$，退化成链时为 $O(n)$。极深链是否触及栈上限取决于运行环境，复杂度分析不能把递归栈忽略掉。

关键点总结

「删除满足某条件的节点」类问题，把递归函数的返回值定义成「剪枝后的子树根」，返回 null 表示整棵删光。这个约定让「删除」这个动作退化成父层的一次赋值 node.left = dfs(node.left, ...)，是所有树剪枝题的统一骨架。

全称条件要转成存在条件再写代码：「所有路径都不足才删」不好判，「存在一条路径达标就留」可以由子树的返回值直接给出。遇到「所有 / 任意」的定义先做一次逻辑取反，往往能让递归的返回值语义变得干净。

「反复删除直到不动点」这类描述，多数时候可以用一趟后序遍历替代——子树先定型，父节点看到的就是最终结果，不存在需要回头修正的情况。看到「重复执行直到无法继续」先想想能不能自底向上一次完成。

叶子分支必须先于内部节点分支判断，因为叶子也满足「左右孩子都为空」；顺序写反会把所有叶子无条件删除，进而删空整棵树。

面试视角：本题的三个高频追问分别是「为什么不用反复遍历」「叶子判据为什么是严格小于」「节点值为负会不会影响提前剪枝」。第三个的答案是：值可负则路径和不单调，不能中途判定失败，必须走到叶子结算——这也是本题与 112 路径总和在剪枝上的关键差异。

易错点总结

错误写法：叶子分支写在内部节点分支之后（先递归再判叶子）：root = [1, 2, 3]、limit = 4 → 叶子 2 和 3 先对两个空孩子递归得到 null，随即落进「左右都空则删除」的分支被无条件删掉，连锁把整棵树删空返回 null，正确答案是 [1, null, 3]。

错误写法：递归结果不回写，写成 dfs(node.left, ...) 而丢弃返回值：root = [1, 2, 3]、limit = 4 → 该删的左孩子 2 仍挂在树上，返回 [1, 2, 3]，正确答案是 [1, null, 3]。

错误写法：叶子判据写成 node.val <= need：root = [1, 2]（根 1、左孩子 2）、limit = 3 → 递归到叶子时 need = 2，路径和恰好等于阈值应当保留；误用 <= 会把叶子删掉，进而删空整棵树，正确答案是 [1, 2]。

错误写法：递归时传 limit 而不是 limit - node.val：root = [1, 2, 3]、limit = 4 → 祖先的贡献从未被扣除，叶子 3 与 limit = 4 相比被判为不足而删除，正确答案是保留它（1 + 3 = 4）。

错误写法：递归时扣孩子的值，写成 dfs(node.left, need - node.left.val)：root = [1, 2, 3]、limit = 4 → 左叶子的判据变成 2 >= 4 - 2，相当于把孩子值算了两次、漏掉根值，于是错误保留路径和仅为 3 的左支；而且孩子可能为空，直接访问还会触发空指针异常。

错误写法：只在递归前检查孩子是否都为空，递归后不再检查：root = [1, 1, 1]、limit = 3 → 两条原始路径和都只有 2，左右叶子会被剪掉；若不在回溯后重新判断，根会作为新叶被错误保留，正确结果是空树。

错误写法：为了「提前剪枝」而在累积和已超过 limit 时直接返回整棵子树：root = [10, -100, 5]、limit = 5 → 根的值已达 10 ≥ 5，误以为整棵子树都达标而全部保留；实际上左路径 10 + (-100) = -90 < 5，节点 -100 必须删除。节点值可为负，路径和不单调，不存在可提前判定的时机。

错误写法：把「不足节点」理解成「存在一条不足路径就删」：root = [1, 2, 3]、limit = 4 → 经过根的路径有 1+2=3（不足）与 1+3=4（达标），按错误理解会把根删掉返回 null，正确答案是 [1, null, 3]。定义里是「所有路径都不足」。

低效写法：物化每条根到叶路径，达标后再逐个标记路径节点：同一祖先会被多个叶子反复处理，最坏需要 $O(nh)$ 时间和额外路径/标记空间；后序遍历把子树结论向上传递，只需 $O(n)$ 时间。

错误写法：写成「删一轮后若有变化就再删一轮」的循环：root 为一条长链 → 每轮只能删掉最深的一个节点，需要 $O(n)$ 轮、每轮 $O(n)$，总共 $O(n^2)$。后序回溯已经把传递删除一次性完成了。

相似题目

题目	难度	考察点
814. 二叉树剪枝	中等	同样是「返回剪枝后子树根」的骨架，判据换成子树是否全为 0，不需要向下传参
1325. 删除给定值的叶子节点	中等	同为「删完可能产生新叶子」的连锁删除，后序遍历一趟完成，可对照本题理解为何无需多轮
669. 修剪二叉搜索树	中等	利用 BST 的有序性，越界时直接返回某一侧子树的递归结果，剪枝方向由值域决定
112. 路径总和	简单	只判断是否存在达标路径，同样向下传剩余额度，但返回布尔且可提前短路
113. 路径总和 II	中等	要输出全部达标路径，必须真的维护路径列表并手写回溯撤销
437. 路径总和 III	中等	路径不必从根开始，需要用前缀和加哈希表统计，与本题的「必须整条根到叶」形成对照
979. 在二叉树中分配硬币	中等	递归返回的是「子树的净盈余」这一数值语义，展示了同一骨架下返回值可以承载什么