XingHuiSama の博客

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

‍

示例 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 按 严格递增 顺序排列

‍

1. 算法核心思想：分治法与“中点即根”

这道题的题眼在于“升序数组”和“平衡二叉搜索树”。

二叉搜索树的特性：左边小，右边大。而升序数组天然满足“左边小，右边大”的顺序。
平衡的特性：要求左右子树高度差不超过 1，也就是要求左右两边的节点数量尽可能一样多。

为了满足这两个苛刻的条件，我们采用分治法（Divide and Conquer）：既然要左右平分，那我们就直接“擒贼先擒王”——每次都精准地把数组最中间的数字揪出来，让它当总根节点！ 这样一来，中间节点左边的数字，天然比它小，且数量刚好占一半，完美构成左子树；右边的数字天然比它大，且数量也占一半，完美构成右子树。

2. 代码逻辑拆解

主函数 sortedArrayToBST：充当启动器的角色。获取数组的真实物理边界 left = 0 和 right = len - 1，然后将建树的重任直接外包给辅助递归函数 func。
递归函数 func：
- 防坠崖（Base Case）：if (left > right)。当我们不断把区间一切为二，直到区间里没有元素时，立刻返回 NULL（这就是叶子节点底下的空指针）。
- 立根节点：通过 (left + right) / 2 算出中间索引 mid，并将其包装成真实的树节点 node。
- 下放权力（递归）：
  - 左子树的领地是 [left, mid - 1]，调用 func 捏好后接在 node->left 上。
  - 右子树的领地是 [mid + 1, right]，调用 func 捏好后接在 node->right 上。
- 层层上报：向上级返回组装好的 node。

‍

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 边界保护：如果数组为空，直接返回空树
        if (nums.size() == 0) {
            return NULL;
        }

        int left = 0;
        int right = nums.size() - 1;
        
        // 调用辅助函数，传入数组的左右边界
        return func(left, right, nums);
    }

    // 辅助函数：负责把 nums[left ... right] 范围内的数字捏成一棵平衡 BST
    TreeNode* func(int left, int right, vector<int>& nums) {
        // 1. 递归终止条件：左边界跑到了右边界的右边，说明这段区间没数字了
        if (left > right) {
            return NULL;
        }

        // 2. 找中点：选择中间的数字作为当前的根节点
        int mid = (left + right) / 2;
        TreeNode* node = new TreeNode(nums[mid]);

        // 3. 分治递归：
        // 中点左边的所有数字，全都交给左孩子去建树
        node->left = func(left, mid - 1, nums);
        // 中点右边的所有数字，全都交给右孩子去建树
        node->right = func(mid + 1, right, nums);

        // 4. 把建好的这棵小树，向上级返回
        return node;
    }
};

3. 复杂度分析

时间复杂度：O**(N)**。其中 N 是数组的长度。每次递归调用 func 都会消耗 O(1) 的时间去创建一个 TreeNode，总共需要创建 N 个节点，因此时间复杂度为 O(N)。
空间复杂度：O**(logN)**。由于我们每次都严格选择中点作为根节点，这棵树是一棵极其标准的平衡二叉树，树的高度为 logN。所以递归调用时系统消耗的栈空间深度最大为 O(logN)。（注意：我们通过传递 left 和 right 指针代替了数组的真实切割拷贝，完美省下了 O*(N) 的额外数组存储空间。*）

‍