• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
iOS开发之OC 和 Swift混编发布时间:2022-07-13
下一篇:
Swift In Depth发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap