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

---

题目

描述： 给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树（BST）。 平衡二叉树是指该树所有节点的左右子树的深度相差不超过 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]

---

解题思路

核心方法

递归法：利用二叉搜索树的性质（左子树所有节点值 < 根节点值 < 右子树所有节点值），以及有序数组的特性，每次选择数组中间元素作为根节点，递归构建左右子树，从而保证树的平衡。

算法步骤

1. 终止条件：当左边界 l > 右边界 r 时，返回 null。
2. 选择中间节点：计算当前数组的中间位置 mid，将该位置的元素作为当前子树的根节点。
3. 递归构建左子树：使用数组左半部分（[l, mid-1]）构建左子树。
4. 递归构建右子树：使用数组右半部分（[mid+1, r]）构建右子树。
5. 返回根节点：返回当前构建的根节点。

---

代码实现

递归法（Java）

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, l, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, r);
        return root;
    }
}

---

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素会被访问一次，用于构建节点。
• 空间复杂度：O(log n)，递归栈的深度取决于树的高度，由于是平衡二叉树，高度为 log n。

---

总结

1. 该方法通过选择中间元素作为根节点，保证了左右子树的节点数相差不超过 1，从而构建出平衡二叉搜索树。
2. 递归过程简洁，符合二叉搜索树和有序数组的特性，时间效率高。
3. 由于数组是升序的，中间元素作为根节点可以确保左子树所有节点值小于根节点，右子树所有节点值大于根节点。

---