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

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
深度优先搜索 树 二叉树

题目描述

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

image-20260929073612592

image-20260929073612705

image-20260929073612845

题意分析

若一个节点所经过的所有原始根到叶路径，其节点值总和都严格小于 limit，就删除这个节点。只要存在一条经过它的路径达到或超过阈值，它就需要保留。返回删除后的根，整棵树可能被删空。

这里判断的是原树中的完整根到叶路径，所有不足节点应同时删除。不能把删去孩子后新出现的叶子，当成一条原本不存在的较短路径重新评估。节点值可以为负，路径和也不一定随着向下走而增大。

解法：DFS 剪枝

核心思路

[!blue]

把最终保留部分理解为所有达标根到叶路径的并集：一个节点位于至少一条达标路径上，就保留；没有任何达标路径经过它，就删除。每个节点只需知道它下面是否仍存在能完成阈值要求的原始叶子。

定义 dfs(node, need) 返回剪枝后的子树根，其中 need 是从当前节点开始还需要达到的路径和，等于 limit 减去全部祖先值之和，尚未扣除当前值。空节点直接返回空。

若当前节点在进入递归时就是叶子，完整路径已经走到末端，只需检查 node.val >= need。相等也算达标；不足时返回空，达标时返回原节点。这一步必须在修改孩子之前进行，才能识别原始叶子。

若原来是内部节点，分别递归左右孩子，将剩余要求更新为 need - node.val。把两个返回值接回当前节点后，只要还有一个孩子保留，就说明至少存在一条达标原路径经过当前节点，它也应保留；若两个孩子都为空，则所有原路径都不足，当前节点也必须返回空。

返回值同时表达是否存在合格路径，以及剪枝后的真实连接。父节点必须接回子调用的返回值，返回空才会实际断开旧孩子，最外层才能取得可能变化的根。

由于后面的值可能为负，当前累计和达到阈值并不保证最终仍达标；后面的正值也可能补足当前缺口。因此不能凭中间路径和提前保留或删除整棵子树，必须在原始叶子处结算。

解题步骤

  1. 从根调用 dfs(root, limit)，将返回值作为最终结果。
  2. 空节点返回空；原始叶子按当前值与剩余要求比较，决定保留或删除。
  3. 对原内部节点，将 need - node.val 传给左右孩子，并接回各自剪枝结果。
  4. 两边都删空时返回空，否则返回当前节点。

代码实现

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        return dfs(root, limit);
    }

    // need 是从当前节点开始还需达到的路径和，尚未扣除当前值。
    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)
}

// need 是从当前节点开始还需达到的路径和，尚未扣除当前值。
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)$，每个节点只访问一次，子树结果合并为常数工作。
  • 空间复杂度：$O(h)$，h 为树高，来自递归调用栈；连接在原树上修改，不复制整棵树。

关键点总结

[!green]

  • 保留条件是存在一条达标路径，删除条件是所有原始路径都不足。
  • 先识别原始叶子，再递归剪孩子，不能对新形成的叶子重新结算。
  • 剩余阈值向下传，修改后的子树根向上返回，两种信息承担不同作用。

易错点总结

[!yellow]

  • 将不足写成小于等于，会错误删除路径和恰好等于阈值的节点。
  • 子调用返回空后没有接回孩子字段，旧连接仍然存在，实际树不会被正确剪掉。
  • 孩子删空后重新按当前短路径判定叶子，会保留不属于任何原始达标路径的节点。
  • 当前和达标就停止下降，忽略后续负数可能让完整路径重新不足。
  • 当前和不足就立刻删除，忽略后续正数可能补足差额。
  • 只要求左右任意一条路径不足就删除当前节点，会把另一条仍达标的分支一起丢掉。

相似题目

题目 难度 关联与区别
814. 二叉树剪枝 中等 同样后序决定是否保留子树，本题还依赖从根传入的路径和，而不只是子树自身含哪些值。
112. 路径总和 简单 根到叶路径求和是基础，本题按至少limit判断，并删除不属于任何合格原路径的节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/67518301
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！