feat: add swift implementation to lcci problem: No.04.12 (doocs#2662)

klever34 · web-flow · commit 426f993fc0d5 · 2024-04-25T18:47:56.000+08:00
diff --git a/lcci/04.12.Paths with Sum/README.md b/lcci/04.12.Paths with Sum/README.md
@@ -257,6 +257,48 @@ impl Solution {
 }
 ```
 
+```swift
+/* class TreeNode {
+*    var val: Int
+*    var left: TreeNode?
+*    var right: TreeNode?
+*
+*    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
+*        self.val = val
+*        self.left = left
+*        self.right = right
+*    }
+* }
+*/
+
+class Solution {
+    private var cnt: [Int: Int] = [:]
+    private var target: Int = 0
+
+    func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
+        cnt[0] = 1
+        target = sum
+        return dfs(root, 0)
+
+    }
+
+    private func dfs(_ root: TreeNode?, _ s: Int) -> Int {
+        guard let root = root else {
+            return 0
+        }
+        let newSum = s + root.val
+        let ans = cnt[newSum - target, default: 0]
+
+        cnt[newSum, default: 0] += 1
+        let leftPaths = dfs(root.left, newSum)
+        let rightPaths = dfs(root.right, newSum)
+        cnt[newSum, default: 0] -= 1
+
+        return ans + leftPaths + rightPaths
+    }
+}
+```
+
 <!-- tabs:end -->
 
 <!-- end -->
diff --git a/lcci/04.12.Paths with Sum/README_EN.md b/lcci/04.12.Paths with Sum/README_EN.md
@@ -269,6 +269,47 @@ impl Solution {
 }
 ```
 
+```swift
+/* class TreeNode {
+*    var val: Int
+*    var left: TreeNode?
+*    var right: TreeNode?
+*
+*    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
+*        self.val = val
+*        self.left = left
+*        self.right = right
+*    }
+* }
+*/
+
+class Solution {
+    private var cnt: [Int: Int] = [:]
+    private var target: Int = 0
+
+    func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
+        cnt[0] = 1
+        target = sum
+        return dfs(root, 0)
+    }
+
+    private func dfs(_ root: TreeNode?, _ s: Int) -> Int {
+        guard let root = root else {
+            return 0
+        }
+        let newSum = s + root.val
+        let ans = cnt[newSum - target, default: 0]
+
+        cnt[newSum, default: 0] += 1
+        let leftPaths = dfs(root.left, newSum)
+        let rightPaths = dfs(root.right, newSum)
+        cnt[newSum, default: 0] -= 1
+
+        return ans + leftPaths + rightPaths
+    }
+}
+```
+
 <!-- tabs:end -->
 
 <!-- end -->
diff --git a/lcci/04.12.Paths with Sum/Solution.swift b/lcci/04.12.Paths with Sum/Solution.swift
@@ -0,0 +1,38 @@
+/* class TreeNode {
+*    var val: Int
+*    var left: TreeNode?
+*    var right: TreeNode?
+*    
+*    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
+*        self.val = val
+*        self.left = left
+*        self.right = right
+*    }
+* } 
+*/
+
+class Solution {
+    private var cnt: [Int: Int] = [:]
+    private var target: Int = 0
+
+    func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
+        cnt[0] = 1
+        target = sum
+        return dfs(root, 0)
+    }
+
+    private func dfs(_ root: TreeNode?, _ s: Int) -> Int {
+        guard let root = root else {
+            return 0
+        }
+        let newSum = s + root.val
+        let ans = cnt[newSum - target, default: 0]
+        
+        cnt[newSum, default: 0] += 1
+        let leftPaths = dfs(root.left, newSum)
+        let rightPaths = dfs(root.right, newSum)
+        cnt[newSum, default: 0] -= 1
+        
+        return ans + leftPaths + rightPaths
+    }
+}
