给你一个整数数组 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:
- 根据分析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]
考察要点:
- 树
- 二叉搜索树
- 数组
- 分治
- 二叉树
