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

LeetCode

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

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

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

例如:

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

      0
     / \
   -3   9
   /   /
 -10  5

方案：

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

举例： -10， -8， -5， 0， 1， 3， 9

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

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

      0
    /   \
  -8      3
  / \    /  \
-10  5  1     9
        

代码：

/**
 * 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我哦。