[Swift]LeetCode1080.根到叶路径上的不足节点|InsufficientNodesinRoottoLeafPaths ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

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

Example 2:

Input: root = 22

Output: [5,4,8,11,null,17,4,7,null,null,null,5]

Note:

The given tree will have between 1 and 5000 nodes.
-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 }