前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Swift 将有序数组转换为二叉搜索树 - LeetCode

Swift 将有序数组转换为二叉搜索树 - LeetCode

作者头像
韦弦zhy
发布2018-12-24 11:13:17
7920
发布2018-12-24 11:13:17
举报
文章被收录于专栏:韦弦的偶尔分享

LeetCode

题目: 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

例如:

给定有序数组: [-10,-3,0,5,9], 一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

代码语言:javascript
复制
      0
     / \
   -3   9
   /   /
 -10  5
方案:

一个有序数组转换为二叉搜索树,则数组中间值(本例:0)则为所求二叉搜索树的根,所以可以采用二分法加递归解题。

举例: -10, -8, -5, 0, 1, 3, 9

** 中间值: **0 -> -8 -> 3

最后转换为如下二叉搜索树:

代码语言:javascript
复制
      0
    /   \
  -8      3
  / \    /  \
-10  5  1     9
代码:
代码语言:javascript
复制
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        if nums.isEmpty { return nil }
        return getTree(nums, 0, nums.count - 1)
    }
    
    func getTree(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        guard left <= right else { return nil }
        let mid = (left + right) / 2
        let node = TreeNode(nums[mid])
        //对mid索引的处理不能忘记
        node.left = getTree(nums, left, mid - 1)
        node.right = getTree(nums, mid + 1, right)
        return node
    }
}
执行用时:52ms
用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.12.05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目: 将有序数组转换为二叉搜索树
    • 例如:
      • 方案:
        • 代码:
          • 执行用时:52ms
            • 用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档