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

对于算法题，按题型类别刷题才会更有成效，因此我这里在网上搜索并参考了下 “🔥 LeetCode 热题 HOT 100” 的题型归类，并在其基础上做了一定的完善，希望能够记录自己的刷题历程，有所收获！点击下发链接跳转~??????

🔥 LeetCode 热题 HOT 100【题型归类汇总，助力刷题】

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

??

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

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

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?按?严格递增?顺序排列

思路：参考?LeetCode题解

• 二叉搜索树BST 的【中序遍历】是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树

• 虽然我们可以以升序序列中的任一个元素作为根节点

• 但是因为本题要求【高度平衡】，因此我们需要选择升序序列的【中间元素】作为根节点奥～

时间复杂度：O(n)，其中?n?是数组的长度。每个数字只访问一次。

空间复杂度：O(logn)，其中 n?是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(log?n)。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 参考题解：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solutions/313508/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/?envType=study-plan-v2&envId=top-100-liked
// BST 的【中序遍历】是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树
// 虽然我们可以以升序序列中的任一个元素作为根节点
// 但是因为本题要求【高度平衡】，因此我们需要选择升序序列的【中间元素】作为根节点奥～
func sortedArrayToBST(nums []int) *TreeNode {
    var dfs func(l, r int) *TreeNode
    dfs = func(l, r int) *TreeNode {
        if l > r {
            return nil
        }

        mid := l + (r-l)/2
        root := &TreeNode{}
        root.Val = nums[mid]
        root.Left = dfs(l, mid-1) // r向左，即中间位置移动
        root.Right = dfs(mid+1, r) // l向右，即向中间位置移动
        return root
    }
    
    return dfs(0, len(nums)-1)
}

题目扩展：

• 109. 有序链表转换二叉搜索树
• 将本题的数组换成了链表，做法完全一样，不过链表无法像数组一样直接索引到中间元素，链表找中间节点可以用快慢指针法，详见：876. 链表的中间结点。