当前位置：首页 > web >正文

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

web 2025/9/7 8:18:39

题目描述

给你一个整数数组 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，即空区间）。

算法过程

初始化递归：调用辅助函数 buildBST，传入数组 nums 及初始区间 [0, nums.length)（覆盖整个数组）。
递归终止条件：若区间 start >= end（空区间，无元素可构建节点），返回 null。
构建当前根节点：
- 计算区间中点 mid = start + Math.floor((end - start) / 2)（用此写法避免 start + end 溢出）；
- 以 nums[mid] 为值创建当前根节点，确保根节点是区间中间元素，左右子树元素数量差≤1（保证平衡）。
递归构建子树：
- 左子树：用左子区间 [start, mid) 递归构建（元素均小于当前根，满足BST左子树特性）；
- 右子树：用右子区间 [mid+1, end) 递归构建（元素均大于当前根，满足BST右子树特性）。
返回结果：递归回溯时，返回当前根节点，最终形成完整的平衡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) {// 终止条件：空区间（无元素可构建节点），返回nullif (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，天然满足“平衡”要求；同时，左子数组元素均小于中间元素、右子数组均大于中间元素，满足BST的数值特性。
为何用左闭右开区间？
左闭右开区间的终止条件 start >= end 更简洁（空区间直接返回null），且子区间划分无需调整边界（左子树 [start, mid)、右子树 [mid+1, end)，无重叠且覆盖原区间），避免左闭右闭区间中 start > end 的复杂判断。
中点计算的溢出问题
若直接写 mid = Math.floor((start + end) / 2)，当 start 和 end 均接近最大值时，start + end 可能超出JavaScript整数安全范围，导致计算错误；而 start + Math.floor((end - start) / 2) 可避免此问题，结果与前者一致且更安全。