[Swift]LeetCode95.不同的二叉搜索树II|UniqueBinarySearchTreesII

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

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

36ms

 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 generateTrees(_ n: Int) -> [TreeNode?] {
16         if n == 0{
17             return [TreeNode?]()
18         }
19         
20         return build(1, n)
21     }
22     
23     func build(_ start : Int, _ end : Int) -> [TreeNode?]{
24         var res = [TreeNode?]()
25         if(start > end){
26             res.append(nil)
27             return res
28         }
29         if(start == end){
30             var node = TreeNode(start)
31             res.append(node)
32             return res
33         }
34         
35         for i in start...end {
36             var left = build(start, i-1)
37             var right = build(i+1, end)
38             for leftNode in left{
39                 for rightNode in right{
40                     var node = TreeNode(i)
41                     node.left = leftNode
42                     node.right = rightNode
43                     res.append(node)
44                 }
45             }
46             
47         }
48         return res
49     }
50 }

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     func generateTrees(_ n: Int) -> [TreeNode?] {
16         if n == 0 {return []}
17         return genTrees(start: 1, end: n)
18     }
19     func genTrees (start: Int, end: Int) -> [TreeNode?] {
20         var ret: [TreeNode?] = []
21         if start > end {
22             ret.append(nil)
23             return ret
24         } else if start == end {
25             var node = TreeNode(start)
26             ret.append(node)
27             return ret
28         }
29         var left: [TreeNode?] = []
30         var right: [TreeNode?] = []
31         for i in start ... end {
32             left = genTrees(start: start, end: i - 1)
33             right = genTrees(start: i + 1, end: end)
34             for left_node in left {
35                 for right_node in right {
36                     let root = TreeNode(i)
37                     root.left = left_node
38                     root.right = right_node
39                     ret.append(root)
40                 }
41             }
42         }
43         return ret
44     }
45 }

60ms

 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 generateTrees(_ n: Int) -> [TreeNode?] {
16         if n == 0 { return [TreeNode?]() }
17         if n == 1 { return [TreeNode(1)] }
18         var matrix = [[TreeNode?]]()
19         matrix.append([nil])
20         matrix.append([TreeNode(1)])
21         
22         func helper(array: [Int]) -> [TreeNode?] {
23             if array.count == 0 {
24                 return [nil]
25             } else if array.count == 1 {
26                 return [TreeNode(array[0])]
27             } else {
28                 var result = [TreeNode?]()
29                 for i in 0 ..< array.count {
30                     
31                     var temp = i == 0 ? [Int]() : Array(array[0...i - 1])
32                     let leftArray = helper(array: temp)
33                     temp = i == array.count - 1 ? [Int]() : Array(array[i + 1...array.count - 1])
34                     let rightArray = helper(array: temp)
35                     for left in leftArray {
36                         for right in rightArray {
37                             let root = TreeNode(array[i])
38                             root.left = left
39                             root.right = right
40                             result.append(root)
41                         }
42                     }
43                     
44                 }
45                 return result
46             } 
47         }
48         
49         return helper(array: Array(1 ... n))
50     }
51 }