1080. Insufficient Nodes in Root to Leaf Paths

题目信息

题号:

1080

难度:

Medium

主题:

二叉树、根到叶路径、节点删除

原题:

LeetCode 1080

重点:

若经过某节点的每条原始根到叶路径总和都严格小于 limit,该节点不足并需删除;删除父节点会连同其子树移除

题目重述

给定一棵二叉树和整数 limit。对原树中的每条根到叶路径,计算路径上所有节点值之和。若某个节点所处的每一条根到叶路径之和都严格小于 limit,则该节点称为不足节点。

删除所有不足节点及其下方仍连接的子树,并返回删除后的根节点。若根节点本身不足,整棵树会被删除并返回 null;路径和可以包含负数节点值。

树中节点数在 [1, 5000] 范围内,-10^5 <= Node.val <= 10^5,-10^9 <= limit <= 10^9。

自建示例

同一根节点只要存在一条达标路径就会保留:

输入:root = [1,2,3], limit = 4
输出:[1,null,3]
解释:经过节点 2 的唯一根到叶路径和为 3,小于 4,因此删除节点 2;经过节点 3 的路径和为 4,节点 3 和根节点都得以保留。

所有根到叶路径都低于限制:

输入:root = [1,-2,-3], limit = 0
输出:null
解释:两条根到叶路径和分别为 -1 和 -2,都严格小于 0,因此根节点也属于不足节点,整棵树被删除。