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

拆解 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(valundefined?0:val)this.left(leftundefined?null:left)this.right(rightundefined?null:right)}}// 主函数将有序数组转换为平衡BSTfunctionsortedArrayToBST(nums:number[]):TreeNode|null{// 递归辅助函数处理[left, right]区间的数组返回构建好的子树根节点constdfs(left:number,right:number):TreeNode|null{// 递归终止条件当左边界大于右边界说明当前区间没有元素返回空节点if(leftright)returnnull;// 1. 找到当前区间的中间元素作为根节点constmidMath.floor((leftright)/2);// 2. 创建当前根节点左右子树暂时设为null后续递归填充constcurNodenewTreeNode(nums[mid],null,null);// 3. 递归构建左子树处理[left, mid-1]区间中间元素左边的元素curNode.leftdfs(left,mid-1);// 4. 递归构建右子树处理[mid1, right]区间中间元素右边的元素curNode.rightdfs(mid1,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是为了处理数组长度为偶数的情况比如数组长度为4mid取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。五、总结解题核心与拓展这道题的核心的是“利用升序数组特性 分治递归 中间元素作为根”本质上是BST中序遍历的反向应用——已知中序序列构建平衡BST。拓展思考如果题目给出的是BST的中序遍历序列不一定是数组但也是升序解题思路完全一致如果数组是降序的只需调整中间元素的选择或交换左右子树的构建顺序同样可以构建平衡BST。这道题难度不高但思路很经典掌握这种“分而治之”的递归思想能为后续解决二叉树的复杂题目打下基础。