[Swift]LeetCode108.将有序数组转换为二叉搜索树|ConvertSortedArraytoBinarySearchTr ...

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

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

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

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

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

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

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  5

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 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 }