★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（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.)
A 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:
Input: root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1
Output: [1,2,3,4,null,null,7,8,9,null,14]
Example 2:
Input: root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22
Output: [5,4,8,11,null,17,4,7,null,null,null,5]
Note:
- The given tree will have between
1and5000nodes. -10^5 <= node.val <= 10^5-10^9 <= limit <= 10^9
给定二叉树的根 root，考虑所有从根到叶的路径：从根到任何叶的路径。 （叶节点是没有子节点的节点。）
如果交于节点 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 = [5,-6,-6], limit = 0 输出：[]
提示：
- 给定的树有
1到5000个节点 -10^5 <= node.val <= 10^5-10^9 <= limit <= 10^9
128ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? { 16 var newRoot = root 17 let sufficient = isSufficientSubset(&newRoot, limit, 0) 18 if !sufficient{ 19 return nil 20 } 21 22 return newRoot 23 } 24 25 func isSufficientSubset(_ root:inout TreeNode?, _ limit: Int,_ currentSum:Int) -> Bool{ 26 guard let root = root else{ 27 return currentSum >= limit 28 } 29 30 let leftSuff = isSufficientSubset(&root.left, limit, currentSum + root.val) 31 let rightSuff = isSufficientSubset(&root.right, limit, currentSum + root.val) 32 if !leftSuff { 33 root.left = nil 34 } 35 36 if !rightSuff { 37 root.right = nil 38 } 39 40 return leftSuff || rightSuff 41 } 42 }
132ms
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? { 16 guard let root = root else { return nil } 17 if root.left === root.right { 18 return root.val < limit ? nil : root 19 } 20 if root.left != nil { 21 root.left = sufficientSubset(root.left, limit - root.val) 22 } 23 if root.right != nil { 24 root.right = sufficientSubset(root.right, limit - root.val) 25 } 26 return root.left === root.right ? nil : root 27 } 28 }
Runtime: 152 ms
Memory Usage: 21.4 MB
1 class Solution { 2 func sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? { 3 let res:Pair = helper(root, 0, limit) 4 return res.node 5 } 6 7 func helper(_ root: TreeNode?,_ cur:Int, _ limit: Int) -> Pair 8 { 9 var left:Pair? = nil 10 var right:Pair? = nil 11 12 if root != nil && root?.left == nil && root?.right == nil 13 { 14 if cur + root!.val < limit 15 { 16 return Pair(nil, root!.val) 17 } 18 else 19 { 20 return Pair(root, root!.val) 21 } 22 } 23 24 var max_val = Int.min 25 if root?.left != nil 26 { 27 left = helper(root?.left, cur + root!.val, limit) 28 max_val = max(left!.max_val, max_val) 29 } 30 31 if root?.right != nil 32 { 33 right = helper(root?.right, cur + root!.val, limit) 34 max_val = max(right!.max_val, max_val) 35 } 36 37 if left != nil && left?.node == nil 38 { 39 root?.left = nil 40 } 41 if right != nil && right?.node == nil 42 { 43 root?.right = nil 44 } 45 46 if (max_val + root!.val + cur < limit) 47 { 48 return Pair(nil, max_val + root!.val); 49 } 50 else 51 { 52 return Pair(root, max_val + root!.val) 53 } 54 } 55 } 56 57 class Pair 58 { 59 var node:TreeNode? 60 var max_val:Int 61 62 init(_ n:TreeNode?,_ v:Int) 63 { 64 self.node = n 65 self.max_val = v 66 } 67 }