1080. Insufficient Nodes in Root to Leaf Paths¶
题目信息¶
- 题号:
1080
- 难度:
Medium
- 主题:
二叉树、根到叶路径、节点删除
- 原题:
- 重点:
若经过某节点的每条原始根到叶路径总和都严格小于
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,因此根节点也属于不足节点,整棵树被删除。