[Swift]LeetCode95. 不同的二叉搜索树 II | Unique Binary Searc

发布时间：2020-12-14 05:10:00 所属栏目：百科来源：网络整理

导读：Given an integer? n ,generate all structurally unique?BST‘s?(binary search trees) that store values 1 ...? n . Example: Input: 3Output:[? [1,null,3,2],? [3,2,1],1,? [2,3],? [1,3]]Explanation:The above output corresponds to the 5 unique BS

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,1],1,? [2,3],? [1,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,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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!