What is the main pattern used in Insufficient Nodes in Root to Leaf Paths?

The core pattern is binary-tree traversal with state tracking, using DFS to propagate path sums and prune insufficient nodes.

How do I handle negative node values or negative limits?

Ensure that cumulative path sums correctly include negative values and compare them to the limit at leaf nodes to decide pruning.

Can this problem be solved iteratively instead of recursively?

Yes, using an explicit stack to simulate DFS and maintaining path sums, but recursion naturally handles backtracking for pruning decisions.

Do I need to revisit nodes after pruning children?

No, the recursive DFS approach allows pruning decisions to propagate upward without revisiting nodes explicitly.

What should I watch out for when a node has only one child?

Check that pruning logic considers null children correctly; a single child may cause the parent to become insufficient if the only path sum is below the limit.

#1080

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

根到叶路径上的不足节点

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有不足节点，并返回最终二叉树的根节点。假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit ，则该节点被称之为不足节点，需要被删除。叶子节点，就是没有子节点的节点。示例 1…

树深度优先搜索二叉树

题目描述

给你二叉树的根节点 root 和一个整数 limit ，请你同时删除树中所有 不足节点 ，并返回最终二叉树的根节点。

假如通过节点 node 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 limit，则该节点被称之为 不足节点 ，需要被删除。

叶子节点，就是没有子节点的节点。

示例 1：

输入：root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
输出：[1,2,3,4,null,null,7,8,9,null,14]

示例 2：

输入：root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
输出：[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3：

输入：root = [1,2,-3,-5,null,4,null], limit = -1
输出：[1,null,-3,4]

提示：

树中节点数目在范围 [1, 5000] 内
-10⁵ <= Node.val <= 10⁵
-10⁹ <= limit <= 10⁹

lightbulb

解题思路

方法一：递归

我们递归遍历整棵树，对于当前遍历到的节点 $root$ ：

如果 $root$ 为空，那么返回空；否则，我们将 $limit$ 减去当前节点的值，即 $limit = limit - root.val$ ，然后继续执行下述步骤。

如果 $root$ 为叶子节点（即 $root$ 的左右子节点都为空），说明我们已经走完了一条从根节点到叶子节点的路径。如果此时 $limit \gt 0$ ，说明该路径上所有节点的值的和小于 $limit$ ，我们返回空节点，表示删除；否则，说明该路径上所有节点的值的和大于等于 $limit$ ，我们返回 $root$ 。

如果 $root$ 不是叶子节点，那么我们递归调用函数 $sufficientSubset$ ，对 $root$ 的左右子节点分别进行处理，并将返回值分别赋值给 $root$ 的左右子节点。

如果 $root$ 的左右子节点在经过递归调用后变成了空节点，那么说明 $root$ 的左右子树中所有从根节点到叶子节点的路径上所有节点的值的和都小于 $limit$ ，因此我们返回空节点，表示删除 $root$ ；否则，说明 $root$ 的左右子树中存在从根节点到叶子节点上所有节点值的和大于等于 $limit$ 的路径，因此我们返回 $root$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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

speed

复杂度分析

指标	值
时间	complexity is O(n) as each node is visited once during DFS. Space complexity is O(h), where h is the height of the tree, due to recursive call stack usage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about how the path sum is tracked efficiently during traversal.
question_mark
Probe if deletion propagation from leaves to root is handled correctly.
question_mark
Watch for handling negative node values or limits and null children.

warning

常见陷阱

外企场景

error
Forgetting to propagate node deletion upwards when all children are insufficient.
error
Incorrectly computing path sums at non-leaf nodes instead of full root-to-leaf paths.
error
Ignoring edge cases like negative node values or limits, leading to wrong pruning.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Prune nodes where the maximum root-to-leaf path sum is below limit instead of every path.
arrow_right_alt
Return the count of nodes deleted rather than the pruned tree.
arrow_right_alt
Modify the tree in place without creating new nodes to save memory.

help

常见问题

外企场景

继续练习

#1110 删点成林 #1038 从二叉搜索树到更大和树 #1123 最深叶节点的最近公共祖先