[Swift]LeetCode108. 将有序数组转换为二叉搜索树 | Convert Sorted Array to Binary Search Tree
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9709029.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 536ms
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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 return makeTree(nums, 0, nums.count - 1)
17 }
18
19 func makeTree(_ nums: [Int], _ start: Int, _ end: Int) -> TreeNode? {
20 guard start <= end else { return nil }
21
22 let mid = (start + end) / 2
23 let node = TreeNode(nums[mid])
24 node.left = makeTree(nums, start, mid - 1)
25 node.right = makeTree(nums, mid + 1, end)
26 return node
27 }
28 }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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 guard nums.count != 0 else {
17 return nil
18 }
19
20 let root = TreeNode(nums[nums.count / 2])
21 root.left = sortedArrayToBST(Array(nums[0..<nums.count / 2]))
22 root.right = sortedArrayToBST(Array(nums[nums.count / 2 + 1..<nums.count]))
23
24 return root
25 }
26 }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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 guard nums.count > 0 else {
17 return nil
18 }
19
20 guard nums.count > 1 else {
21 let treeNode = TreeNode(nums[0])
22 return treeNode
23 }
24
25 let middleIndex = nums.count/2
26 let treeNode = TreeNode(nums[middleIndex])
27
28
29 let leftSubarray = Array(nums[0..<middleIndex])
30 let rightSubarray = ((middleIndex+1) < nums.count)
31 ? Array(nums[(middleIndex+1)..<nums.count])
32 : []
33
34 let leftNode = sortedArrayToBST(leftSubarray)
35 let rightNode = sortedArrayToBST(rightSubarray)
36
37 treeNode.left = leftNode
38 treeNode.right = rightNode
39 return treeNode
40 }
41 }44ms
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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 return sortedArrayToBST1(nums, 0, nums.count)
17 }
18
19 private func sortedArrayToBST1(_ nums: [Int], _ beg: Int, _ end: Int) -> TreeNode? {
20 if beg == end { return nil }
21 if end - beg == 1 { return TreeNode(nums[beg]) }
22
23 let mid = (beg + end) / 2
24 let node = TreeNode(nums[mid])
25 node.left = sortedArrayToBST1(nums, beg, mid)
26 node.right = sortedArrayToBST1(nums, mid + 1, end)
27 return node
28 }
29 }52ms
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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 if nums.count == 0 {
17 return nil
18 }
19 if nums.count == 1 {
20 return TreeNode(nums[0])
21 }
22
23 let mid = nums.count / 2
24 let root = TreeNode(nums[mid])
25
26 root.left = sortedArrayToBST(Array(nums[0..<mid]))
27 if mid + 1 < nums.count {
28 root.right = sortedArrayToBST(Array(nums[mid+1..<nums.count]))
29 }
30 return root
31 }
32 }1052ms
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 sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
16 if nums.count == 0 {
17 return nil;
18 }
19
20
21
22 return createTree(nums, 0, nums.count - 1)
23 }
24 func createTree(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
25
26 if left > right {
27 return nil
28 }
29
30 let mid = (left + right + 1) / 2
31 let node = TreeNode(nums[mid])
32
33 node.left = createTree(nums, left, mid - 1)
34 node.right = createTree(nums, mid + 1, right)
35
36 return node;
37 }
38 }