feat: add swift implementation to lcci problem: No.04.09 (doocs#2660)

klever34 · web-flow · commit ca67b79e3b25 · 2024-04-25T18:46:02.000+08:00
diff --git a/lcci/04.09.BST Sequences/README.md b/lcci/04.09.BST Sequences/README.md
@@ -21,4 +21,61 @@
 
 ## 解法
 
+<!-- tabs:start -->
+
+```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 {
+    func BSTSequences(_ root: TreeNode?) -> [[Int]] {
+        guard let root = root else { return [[]] }
+
+        var result = [[Int]]()
+        let prefix = [root.val]
+        let leftSeq = BSTSequences(root.left)
+        let rightSeq = BSTSequences(root.right)
+
+        for left in leftSeq {
+            for right in rightSeq {
+                var weaved = [[Int]]()
+                weaveLists(left, right, &weaved, prefix)
+                result.append(contentsOf: weaved)
+            }
+        }
+        return result
+    }
+
+    private func weaveLists(_ first: [Int], _ second: [Int], _ results: inout [[Int]], _ prefix: [Int]) {
+        if first.isEmpty || second.isEmpty {
+            var result = prefix
+            result.append(contentsOf: first)
+            result.append(contentsOf: second)
+            results.append(result)
+            return
+        }
+
+        var prefixWithFirst = prefix
+        prefixWithFirst.append(first.first!)
+        weaveLists(Array(first.dropFirst()), second, &results, prefixWithFirst)
+
+        var prefixWithSecond = prefix
+        prefixWithSecond.append(second.first!)
+        weaveLists(first, Array(second.dropFirst()), &results, prefixWithSecond)
+    }
+}
+```
+
+<!-- tabs:end -->
+
 <!-- end -->
diff --git a/lcci/04.09.BST Sequences/README_EN.md b/lcci/04.09.BST Sequences/README_EN.md
@@ -31,4 +31,61 @@ Given the following tree:</p>
 
 ## Solutions
 
+<!-- tabs:start -->
+
+```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 {
+    func BSTSequences(_ root: TreeNode?) -> [[Int]] {
+        guard let root = root else { return [[]] }
+
+        var result = [[Int]]()
+        let prefix = [root.val]
+        let leftSeq = BSTSequences(root.left)
+        let rightSeq = BSTSequences(root.right)
+
+        for left in leftSeq {
+            for right in rightSeq {
+                var weaved = [[Int]]()
+                weaveLists(left, right, &weaved, prefix)
+                result.append(contentsOf: weaved)
+            }
+        }
+        return result
+    }
+
+    private func weaveLists(_ first: [Int], _ second: [Int], _ results: inout [[Int]], _ prefix: [Int]) {
+        if first.isEmpty || second.isEmpty {
+            var result = prefix
+            result.append(contentsOf: first)
+            result.append(contentsOf: second)
+            results.append(result)
+            return
+        }
+
+        var prefixWithFirst = prefix
+        prefixWithFirst.append(first.first!)
+        weaveLists(Array(first.dropFirst()), second, &results, prefixWithFirst)
+
+        var prefixWithSecond = prefix
+        prefixWithSecond.append(second.first!)
+        weaveLists(first, Array(second.dropFirst()), &results, prefixWithSecond)
+    }
+}
+```
+
+<!-- tabs:end -->
+
 <!-- end -->
diff --git a/lcci/04.09.BST Sequences/Solution.swift b/lcci/04.09.BST Sequences/Solution.swift
@@ -0,0 +1,50 @@
+/* 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 {
+    func BSTSequences(_ root: TreeNode?) -> [[Int]] {
+        guard let root = root else { return [[]] }
+
+        var result = [[Int]]()
+        let prefix = [root.val]
+        let leftSeq = BSTSequences(root.left)
+        let rightSeq = BSTSequences(root.right)
+
+        for left in leftSeq {
+            for right in rightSeq {
+                var weaved = [[Int]]()
+                weaveLists(left, right, &weaved, prefix)
+                result.append(contentsOf: weaved)
+            }
+        }
+        return result
+    }
+
+    private func weaveLists(_ first: [Int], _ second: [Int], _ results: inout [[Int]], _ prefix: [Int]) {
+        if first.isEmpty || second.isEmpty {
+            var result = prefix
+            result.append(contentsOf: first)
+            result.append(contentsOf: second)
+            results.append(result)
+            return
+        }
+
+        var prefixWithFirst = prefix
+        prefixWithFirst.append(first.first!)
+        weaveLists(Array(first.dropFirst()), second, &results, prefixWithFirst)
+
+        var prefixWithSecond = prefix
+        prefixWithSecond.append(second.first!)
+        weaveLists(first, Array(second.dropFirst()), &results, prefixWithSecond)
+    }
+}
