[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://www.cnblogs.com/strengthen/p/10993155.html 
➤原文地址:https://www.cnblogs.com/strengthen/p/10470993.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)

node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.

 

Example 1:

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths
Output: [1,2,3,4,null,null,7,8,9,null,14]

Example 2:

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths
Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths
Output: [5,4,8,11,null,17,4,7,null,null,null,5] 

Note:

  1. The given tree will have between 1 and 5000 nodes.
  2. -10^5 <= node.val <= 10^5
  3. -10^9 <= limit <= 10^9

给定二叉树的根 root,考虑所有从根到叶的路径:从根到任何叶的路径。 (叶节点是没有子节点的节点。)

如果交于节点 node 的每个根到叶路径的总和严格小于限制 limit,则该节点为不足节点。

同时删除所有不足节点,并返回生成的二叉树的根。 

示例 1:

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

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

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

输出:[1,2,3,4,null,null,7,8,9,null,14]

示例 2:

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

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

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

输出:[5,4,8,11,null,17,4,7,null,null,null,5]

示例 3:

[Swift]LeetCode1080. 根到叶路径上的不足节点 | Insufficient Nodes in Root to Leaf Paths

输入:root = [5,-6,-6], limit = 0
输出:[] 

提示:

  1. 给定的树有 1 到 5000 个节点
  2. -10^5 <= node.val <= 10^5
  3. -10^9 <= limit <= 10^9
 
上一篇:LeetCode 742. Closest Leaf in a Binary Tree


下一篇:Leetcode-5084 Insufficient Nodes in Root to Leaf Paths(根到叶路径上的不足节点)