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

LeetCode 108. 将有序数组转换为二叉搜索树：解题思路+代码详解

news 2026/5/12 17:16:15

拆解 LeetCode 简单难度的经典题目——108. 将有序数组转换为二叉搜索树，这道题不仅考察二叉搜索树（BST）的核心特性，还涉及平衡二叉树的构建技巧，是入门二叉树递归的绝佳例题，新手也能轻松上手，赶紧来看看吧！

一、题目解读：读懂需求，找对方向

题目很简洁：给定一个升序排列的整数数组 nums，要求将其转换为一棵平衡的二叉搜索树。

先明确两个关键概念，避免踩坑：

二叉搜索树（BST）：左子树所有节点值 < 根节点值，右子树所有节点值 > 根节点值，且左右子树也都是BST；
平衡二叉树：左右两个子树的高度差的绝对值不超过1，这样能保证树的查询、插入效率，避免退化成链表。

题目给出的数组是升序的，这是解题的核心突破口——升序数组的特性，恰好和BST的中序遍历结果完全一致（BST中序遍历是升序序列）。而我们要做的，就是根据这个中序序列，反向构建出一棵平衡的BST。

二、核心思路：为什么选“中间元素”当根？

要构建平衡BST，最关键的一步是选择合适的根节点。如果随便选一个元素当根，很可能导致一边子树过长，无法满足平衡要求。

这里有个最优策略：每次选择数组的中间元素作为当前子树的根节点。

原因很简单：

中间元素左边的元素，自然构成左子树（都比中间元素小，符合BST左子树规则）；
中间元素右边的元素，自然构成右子树（都比中间元素大，符合BST右子树规则）；
左右子树的元素个数相差最多1，这样构建出的子树高度差不会超过1，天然满足平衡要求。

这是一种“分而治之”的思路，和二分查找的逻辑高度相似——每次将数组分成左右两部分，递归处理每一部分，最终构建出完整的平衡BST。

三、递归实现：代码一步步拆解

递归是实现这种分治思路最简洁的方式，我们先看完整代码，再逐行拆解核心逻辑（使用TypeScript编写，和题目给出的代码一致，适配前端/算法刷题场景）。

完整代码

// 二叉树节点类（题目已给出，无需修改）classTreeNode{val:numberleft:TreeNode|nullright:TreeNode|nullconstructor(val?:number,left?:TreeNode|null,right?:TreeNode|null){this.val=(val===undefined?0:val)this.left=(left===undefined?null:left)this.right=(right===undefined?null:right)}}// 主函数：将有序数组转换为平衡BSTfunctionsortedArrayToBST(nums:number[]):TreeNode|null{// 递归辅助函数：处理[left, right]区间的数组，返回构建好的子树根节点constdfs=(left:number,right:number):TreeNode|null=>{// 递归终止条件：当左边界大于右边界，说明当前区间没有元素，返回空节点if(left>right)returnnull;// 1. 找到当前区间的中间元素，作为根节点constmid=Math.floor((left+right)/2);// 2. 创建当前根节点（左右子树暂时设为null，后续递归填充）constcurNode=newTreeNode(nums[mid],null,null);// 3. 递归构建左子树：处理[left, mid-1]区间（中间元素左边的元素）curNode.left=dfs(left,mid-1);// 4. 递归构建右子树：处理[mid+1, right]区间（中间元素右边的元素）curNode.right=dfs(mid+1,right);// 5. 返回当前构建好的子树根节点returncurNode;}// 初始调用：处理整个数组[0, nums.length-1]returndfs(0,nums.length-1);};

核心逻辑拆解

我们重点看递归辅助函数dfs，它是整个解题的核心，接收两个参数：left（当前区间左边界）、right（当前区间右边界），返回当前区间构建的子树根节点。

递归终止条件：if (left > right) return null;

当左边界大于右边界时，说明当前区间没有元素可以构建节点，返回空节点，这是递归的“出口”，避免死循环。

选择根节点：const mid = Math.floor((left + right) / 2);

取区间中间索引，Math.floor是为了处理数组长度为偶数的情况（比如数组长度为4，mid取1或2都可以，最终构建的树可能不同，但都满足平衡BST要求）。

创建根节点：new TreeNode(nums[mid], null, null);

用中间元素的值创建根节点，左右子树先设为null，后续通过递归填充。

递归构建左右子树：

curNode.left = dfs(left, mid - 1)：递归处理左半区间，将返回的子树作为当前根节点的左子树；

curNode.right = dfs(mid + 1, right)：递归处理右半区间，将返回的子树作为当前根节点的右子树。

返回当前子树：将构建好的当前子树根节点返回，供上一层递归使用。

主函数中，我们调用dfs(0, nums.length - 1)，从整个数组的第一个元素到最后一个元素开始构建，最终返回整棵树的根节点。

四、关键注意点：避坑指南

中间索引的计算：除了Math.floor((left + right)/2)，也可以用(left + right) >> 1（位运算，等价于向下取整），效率更高，但可读性稍差，刷题时两种方式都可以。
数组长度为偶数的情况：当数组长度为偶数时，中间元素有两个（比如[1,2,3,4]，mid可以是1或2），两种选择构建的树不同，但都满足平衡BST的要求，题目不要求唯一解，所以两种写法都正确。
递归的边界处理：必须严格判断left > right，不能写成left === right（否则会漏掉最后一个元素，或导致死循环）。
平衡的保证：因为每次都选择中间元素作为根，左右子树的节点数相差最多1，所以每一层的子树都是平衡的，整个树自然是平衡BST。