• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode437.路径总和III|PathSumIII

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

示例:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

40ms
 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     
16     func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
17         var dict = [Int: Int]()
18         dict[0] = 1
19         return getNum(root, 0, sum, &dict)
20     }
21     
22     func getNum(_ rootNode: TreeNode?, _ curSum: Int, _ target: Int, _ dict: inout [Int: Int]) -> Int {
23         guard let root = rootNode else {
24             return 0
25         }
26         var tempSum = curSum
27         tempSum += root.val
28         var res = dict[tempSum-target] ?? 0
29         dict[tempSum] = (dict[tempSum] ?? 0) + 1
30         print(tempSum)
31  
32         res += getNum(root.left, tempSum, target, &dict) + getNum(root.right, tempSum, target, &dict)
33         dict[curSum+root.val] = (dict[curSum+root.val] ?? 0) - 1
34         return res
35     }
36 }

44ms

 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     
16     func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
17         var dict = [Int: Int]()
18         dict[0] = 1
19         return getNum(root, 0, sum, &dict)
20     }
21     
22     func getNum(_ rootNode: TreeNode?, _ curSum: Int, _ target: Int, _ dict: inout [Int: Int]) -> Int {
23         guard let root = rootNode else {
24             return 0
25         }
26         var tempSum = curSum
27         tempSum += root.val
28         var res = dict[tempSum-target] ?? 0
29         dict[tempSum] = (dict[tempSum] ?? 0) + 1
30     
31         res += getNum(root.left, tempSum, target, &dict) + getNum(root.right, tempSum, target, &dict)
32         dict[curSum+root.val] = (dict[curSum+root.val] ?? 0) - 1
33         return res
34     }
35 }

52ms

 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     
16     func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
17         guard let root = root else { return 0 }
18         
19         var result = 0
20         var dict = [Int : Int]()
21         dfs(root, sum, 0, [0 : 1], &result)
22         
23         return result
24     }
25     
26     func dfs(_ root: TreeNode?, _ target: Int, _ prev: Int, _ dict: [Int : Int], _ result: inout Int) {
27         guard let root = root else { return }
28         
29         let sum = root.val + prev
30         if let freq = dict[sum - target] {
31             result += freq
32         }
33         
34         var newDict = dict
35         newDict[sum] = (dict[sum] ?? 0) + 1
36         
37         dfs(root.left, target, sum, newDict, &result)
38         dfs(root.right, target, sum, newDict, &result)
39     }
40 }

84ms

 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     
16     func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
17         guard let root = root else { return 0 }
18         
19         var result = 0
20         var dict = [Int : Int]()
21         dfs(root, sum, 0, [0 : 1], &result)
22         
23         return result
24     }
25     
26     func dfs(_ root: TreeNode?, _ target: Int, _ prev: Int, _ dict: [Int : Int], _ result: inout Int) {
27         guard let root = root else { return }
28         
29         let sum = root.val + prev
30         if let freq = dict[sum - target] {
31             print("sum:\(sum), cur:\(root.val), prev:\(prev)")
32             result += freq
33         }
34         
35         var newDict = dict
36         newDict[sum] = (dict[sum] ?? 0) + 1
37         
38         dfs(root.left, target, sum, newDict, &result)
39         dfs(root.right, target, sum, newDict, &result)
40     }
41 }

172ms

 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 pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
16         
17         guard let root = root else { return 0 }
18         
19         return numberOfPaths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
20     }
21     
22     func numberOfPaths(_ root: TreeNode?, _ sum: Int) -> Int {
23         
24         guard let root = root else { return 0 }
25         
26         let diff = sum - root.val
27         let left = numberOfPaths(root.left, diff)
28         let right = numberOfPaths(root.right, diff) 
29         return  diff == 0 ? 1 + left + right : left + right
30     }
31 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift入门笔记(四)发布时间:2022-07-13
下一篇:
Swift,枚举发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap