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

题目来源：108. 将有序数组转换为二叉搜索树 – 力扣（LeetCode）

📌 题目描述

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

高度平衡：每个节点的左右两个子树的高度差的绝对值不超过 1。

✅ 示例解析

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：

• 根为 0（中间元素）
• 左子树由 [-10, -3] 构成，右子树由 [5, 9] 构成
• 结果是一棵高度平衡的 BST

注：[0,-10,5,null,-3,null,9] 等其他结构只要满足平衡和 BST 性质，也视为正确。

示例 2：

输入：nums = [1,3]
输出：[3,1] 或 [1,null,3]
解释：两种结构高度差均为 1，均合法。

示例 3：

输入：nums = [0]
输出：[0]

⚠️ 提示

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

💡 解法：分治 + 递归（中序构造）—— O(n) 时间，O(log n) 空间

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(0, nums.length - 1, nums);
    }

    public TreeNode dfs(int left, int right, int[] nums) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1; 
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(left, mid - 1, nums);
        root.right = dfs(mid + 1, right, nums);
        return root;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  每个数组元素恰好被访问一次，用于创建一个树节点，总时间 O(n)。
• 空间复杂度：O(log n)
  递归调用栈的深度等于树的高度。由于我们始终选择中点，构造出的树是高度平衡的，高度为 ⌊log₂n⌋ + 1，因此空间复杂度为 O(log n)。
  （不考虑输出树本身占用的空间）

🧩 解题思路

核心思想：分治 + 二叉搜索树性质

• 有序数组的中点作为根节点，能保证左右子树节点数量尽可能相等 → 满足高度平衡。
• 左半部分 [left, mid-1] 构成左子树，右半部分 [mid+1, right] 构成右子树。
• 递归处理左右子数组，自然满足 BST 的定义：左子树所有值 < 根 < 右子树所有值。

为什么选中点？

• 若选最左或最右，会退化为链表（不平衡）；
• 选中点可使左右子树大小最多相差 1，确保平衡。

边界处理：

• 当 left > right 时，说明当前子数组为空，返回 null。