108.将有序数组转换为二叉搜索树

题目#108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

思路分析

一开始拿到这个题目一定会想，平衡二叉树是个啥来这？好像有个要求是左右子树高度差小于等于1，那使用数组构造一个平衡二叉树就很麻烦了，而且题目还要求是一个搜索树，脑海中又出现了搜索树的定义：中序遍历为升序，同时满足这两个条件就很难搞了啊，好了这题放弃，下一题，本篇结束。
哈哈开个玩笑，其实仔细分析题目，还是会发现思路的。注意到题中给的条件是升序数组，那我就将数组的最中间的值当做我的二叉树的根节点值，然后将左右两边分别构造左右子树，那构造出来的左右子树的个数差不超过1，不就满足平衡二叉树了吗，而且这个数组是升序的，我也能想办法满足搜索树了。

代码

fun sortedArrayToBST(nums: IntArray): TreeNode? {
    return buildNode(nums, 0, nums.lastIndex)
}

private fun buildNode(nums: IntArray, start: Int, end: Int): TreeNode? {
    if (start > end) return null
    val mid = (start + end) / 2
    val root = TreeNode(nums[mid])
    root.left = buildNode(nums, start, mid - 1)
    root.right = buildNode(nums, mid + 1, end)
    return root
}

代码分析

由于题中的方法只给了一个入参，如果想要分开数组且只用一个入参，需要涉及到数组值的复制，会额外增加时间复杂度和空间复杂度，所以引入index来指明数组的区域fun buildNode(nums: IntArray, start: Int, end: Int)此时需要分情况讨论

• 起始节点大于终止节点index时，返回的二叉树为空if (start > end) return null
• 否则将区间细分为两个，并将中间节点的值给根节点，很自然的想到使用递归来构造左右子树了
  root.left = buildNode(nums, start, mid - 1)
root.right = buildNode(nums, mid + 1, end)