Submit 95_UniqueBinarySearchTreesII

Binlogo-Archive · Jul 21, 2020 · 77b6712 · 77b6712
1 parent 327f400
commit 77b6712
Show file tree

Hide file tree

Showing 2 changed files with 61 additions and 0 deletions.
diff --git a/...ePlayground.playground/Pages/95_UniqueBinarySearchTreesII.xcplaygroundpage/Contents.swift b/...ePlayground.playground/Pages/95_UniqueBinarySearchTreesII.xcplaygroundpage/Contents.swift
@@ -0,0 +1,57 @@
+//: [Previous](@previous)
+
+import Foundation
+
+
+/// Definition for a binary tree node.
+public class TreeNode {
+    public var val: Int
+    public var left: TreeNode?
+    public var right: TreeNode?
+    public init() { self.val = 0; self.left = nil; self.right = nil; }
+    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
+    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
+        self.val = val
+        self.left = left
+        self.right = right
+    }
+}
+
+class Solution {
+    func generateTrees(_ n: Int) -> [TreeNode?] {
+        let res = [TreeNode?]()
+        if n == 0 {
+            return res
+        }
+        return _generateTrees(start: 1, end: n)
+
+    }
+
+    private func _generateTrees(start:Int, end:Int) -> [TreeNode?]{
+        var res = [TreeNode?]()
+        if start > end {
+            res.append(nil)
+            return res
+        }
+        if start == end {
+            let tmp = TreeNode(start)
+            res.append(tmp)
+            return res
+        }
+        for i in start...end {
+            let leftTrees = _generateTrees(start: start, end: i - 1)
+            let rightTrees = _generateTrees(start: i + 1, end: end)
+            for tmpLeft in leftTrees {
+                for tmpRight in rightTrees {
+                    let root = TreeNode(i)
+                    root.left = tmpLeft
+                    root.right = tmpRight
+                    res.append(root)
+                }
+            }
+        }
+        return res
+    }
+}
+
+//: [Next](@next)
diff --git a/LeetCodePlayground.playground/contents.xcplayground b/LeetCodePlayground.playground/contents.xcplayground
@@ -113,5 +113,9 @@
         <page name='350_IntersectionofTwoArraysII '/>
         <page name='120_Triangle'/>
         <page name='96_UniqueBinarySearchTrees '/>
+        <page name='35_SearchInsertPosition'/>
+        <page name='312_BurstBalloons'/>
+        <page name='785_IsGraphBipartite?'/>
+        <page name='95_UniqueBinarySearchTreesII'/>
     </pages>
 </playground>