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

[此处请插入：有序数组分治转换为平衡二叉搜索树过程示意图]

✨核心逻辑

本题采用 分治法（中序遍历的逆向思维） 的策略：

保持平衡的关键：要求构建的是一棵“高度平衡”的二叉搜索树。对于一个有序数组，选取中间位置的元素作为根节点，能自然保证左右子树的节点数量差值不超过 1，从而最直接地满足平衡要求。
分而治之：选定中间元素作为根节点后，数组被划分为左半部分和右半部分。左半部分数组递归用于构建左子树，右半部分数组递归用于构建右子树。
递归终止条件：当区间左边界 left 大于右边界 right 时，说明区间为空，返回 null。

🔥代码实现（含详细变量注释）

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 从数组的整个范围开始递归构建，返回构建好的树的根节点
        return sortHelp(0, nums.length - 1, nums);
    }
    
    // 递归辅助函数：在数组的 [left, right] 区间内构建二叉搜索树
    // left：当前区间的左边界索引
    // right：当前区间的右边界索引
    // nums：有序整数数组
    public TreeNode sortHelp(int left, int right, int[] nums) {
        // 递归终止条件：当左边界大于右边界时，说明区间内没有元素了，返回空节点
        if (left > right) {
            return null;
        }

        // mid：计算当前区间的中间索引。使用 left + (right - left) / 2 防止整数溢出
        int mid = left + (right - left) / 2;
        // t：以中间元素创建当前的根节点，确保树的高度平衡
        TreeNode t = new TreeNode(nums[mid]);

        // 递归处理左半区间 [left, mid - 1]，构建当前节点的左子树
        TreeNode leftTree = sortHelp(left, mid - 1, nums);
        // 递归处理右半区间 [mid + 1, right]，构建当前节点的右子树
        TreeNode rightTree = sortHelp(mid + 1, right, nums);

        // 将递归构建好的左右子树分别接入到当前根节点
        t.left = leftTree;
        t.right = rightTree;

        // 返回当前构建好的子树根节点
        return t;
    }
}

⏱️复杂度分析
- 时间复杂度：O(N)，其中 N 是数组的长度。每个元素只会被访问一次来创建一个树节点，总访问次数与数组元素数量成正比。
- 空间复杂度：O(log N)（不考虑存储树节点的空间）。主要消耗在递归调用时系统隐式维护的栈空间，递归深度取决于树的高度，最坏情况下（数组转化为链状树）为 O(N)，但因为是选取中间元素构建平衡树，树高稳定在 O(log N)。