初级算法-树-将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序*排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

摘一个示例做个说明.
示例 1：
    0 
   /  \
  -3   9
  /    /  
-15   7
输入：nums = [-15,-3,0,7,9]
输出：[0,-3,9,-15,null,7]
解释：[0,-15,7,null,-3,null,9] 也将被视为正确答案：

条件分析:

1. 升序数组 -> 有序的数据
2. 高度屏风二叉树

解决思路1:

1. 根据分析1、2,采用递归操作.高度平衡的二叉搜索树,也就是每个节点的左右两个子树的高度差的绝对值不超过 1 的二叉树.所以我们采用从上往下的构建过程.首先取出根.因为满足高度平衡的二叉树,所以取根的值为数组的中间值.可以理解为把数组从中间拆分,然后中间值就是root值.左边数据是left树.右边数据是right树.然后递归操作,直到数据取完即可.每次都是相当于取数组区间的中间值.

解决办法

 func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
    return sortedArrayToBST(0, nums.count - 1, nums)
}

 func sortedArrayToBST(_ start: Int, _ end: Int, _ num: [Int]) -> TreeNode?{
    if start > end {
        return nil
    }
    // 取中
    let mid = (start + end) / 2
    let root = TreeNode.init(num[mid])
    // 继续取中
    root.left = sortedArrayToBST(start, mid - 1, num)
    // 继续取中
    root.right = sortedArrayToBST(mid + 1, end, num)
    return root
}

将有序数组转换为二叉搜索树 提交结果.jpg

测试用例:

let nums = [-10,-3,0,5,9]

考察要点:

• 树
• 二叉搜索树
• 数组
• 分治
• 二叉树