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