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

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

原作者: [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 }