【LeetCode热题100道笔记】将有序数组转换为二叉搜索树

题目描述

给你一个整数数组 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 按 严格递增 顺序排列

思考：分治思想构建平衡BST

核心是分治递归：每次取数组中间元素作为当前根节点，将数组分为“左子数组”（根左侧元素）和“右子数组”（根右侧元素），分别递归构建左、右子树——左子数组构建左子树（值均小于根），右子数组构建右子树（值均大于根），最终形成平衡BST。

采用左闭右开区间 [start, end) 划分数组，可简化边界处理（终止条件为 start >= end，即空区间）。

算法过程

1. 初始化递归：调用辅助函数 buildBST，传入数组 nums 及初始区间 [0, nums.length)（覆盖整个数组）。
2. 递归终止条件：若区间 start >= end（空区间，无元素可构建节点），返回 null。
3. 构建当前根节点：
   • 计算区间中点 mid = start + Math.floor((end - start) / 2)（用此写法避免 start + end 溢出）；
   • 以 nums[mid] 为值创建当前根节点，确保根节点是区间中间元素，左右子树元素数量差≤1（保证平衡）。
4. 递归构建子树：
   • 左子树：用左子区间 [start, mid) 递归构建（元素均小于当前根，满足BST左子树特性）；
   • 右子树：用右子区间 [mid+1, end) 递归构建（元素均大于当前根，满足BST右子树特性）。
5. 返回结果：递归回溯时，返回当前根节点，最终形成完整的平衡BST。

时空复杂度

• 时间复杂度：O(n)，n为数组长度。
  原因：每个数组元素仅被用于创建一个节点（递归过程中每个元素对应一个根/子节点），每个节点的构建操作（创建节点、递归调用）均为O(1)，总操作次数与数组长度线性相关。
• 空间复杂度：O(log n)，n为数组长度。
  原因：递归调用栈深度取决于平衡BST的高度——平衡BST的高度为 log n（如n=5时高度2，n=7时高度3），最坏情况下（无额外空间消耗），空间复杂度由递归栈决定，为O(log n)。

代码（左闭右开区间实现）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    // 初始区间：左闭右开 [0, nums.length)，覆盖整个数组
    return buildBST(nums, 0, nums.length);
};

// 辅助函数：基于区间 [start, end) 构建平衡BST
function buildBST(nums, start, end) {
    // 终止条件：空区间（无元素可构建节点），返回null
    if (start >= end) return null;

    // 计算中点：避免 start + end 溢出（如start和end均接近Number.MAX_SAFE_INTEGER）
    const mid = start + Math.floor((end - start) / 2);
    // 以中点元素为根，保证左右子树元素数量差≤1，天然平衡
    const root = new TreeNode(nums[mid]);

    // 递归构建左子树：左子区间 [start, mid)（元素均小于root.val）
    root.left = buildBST(nums, start, mid);
    // 递归构建右子树：右子区间 [mid+1, end)（元素均大于root.val）
    root.right = buildBST(nums, mid + 1, end);

    return root;
}

关键逻辑解析

1. 为何选中间元素为根？
   升序数组的中间元素可将数组分为“长度相等或差1”的左右子数组，递归构建的左右子树高度差≤1，天然满足“平衡”要求；同时，左子数组元素均小于中间元素、右子数组均大于中间元素，满足BST的数值特性。

2. 为何用左闭右开区间？
   左闭右开区间的终止条件 start >= end 更简洁（空区间直接返回null），且子区间划分无需调整边界（左子树 [start, mid)、右子树 [mid+1, end)，无重叠且覆盖原区间），避免左闭右闭区间中 start > end 的复杂判断。

3. 中点计算的溢出问题
   若直接写 mid = Math.floor((start + end) / 2)，当 start 和 end 均接近最大值时，start + end 可能超出JavaScript整数安全范围，导致计算错误；而 start + Math.floor((end - start) / 2) 可避免此问题，结果与前者一致且更安全。