将有序数组转换为二叉搜索树：分治递归的优雅实践

一道经典的二叉树构建题，核心在于理解"平衡"与"搜索"两个约束如何同时被满足，而答案就藏在对数组不断切半的递归过程中。

---

一、题目条件分析

先来拆解题目给出的关键条件：

• 输入是有序数组：数组已经按升序排列，这是整个解法的前提。如果没有"有序"这个条件，问题会复杂得多——我们需要先排序或采用别的策略。而正因为数组有序，我们才有机会利用中间元素来保证平衡。
• 输出是二叉搜索树（BST）：BST 的性质是——左子树所有节点的值 < 根节点的值 < 右子树所有节点的值。这个性质与升序数组的排列天然契合：数组中任意一个元素，它左边的所有值都比它小，右边的所有值都比它大。
• 树必须是平衡的：平衡的定义是，任意节点的左右子树高度差不超过 1。这意味着我们不能把所有元素都挂到一侧，必须尽可能均匀地分配左右子树的节点数量。

这三个条件环环相扣：有序保证了我们可以直接利用位置关系来满足BST 性质，而平衡要求我们在分配节点时做到左右均匀。当三个条件同时被考虑时，一个自然的策略就浮现出来了——取中间元素为根，左右两半分别构建子树。

---

二、思路概览与代码

思路概览

一句话概括：每次取数组中间元素作为根节点，左半部分递归构建左子树，右半部分递归构建右子树，直到无法再分割为止。

这个思路同时满足了两个核心约束：

• BST 性质：因为数组升序，中间元素左边的值都更小、右边的值都更大，天然满足左 < 根 < 右。
• 平衡性质：每次取中间元素，左右两半的元素数量最多相差 1，因此构建出的树高度差不会超过 1。

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicTreeNodesortedArrayToBST(int[]nums){returnbuildTree(nums,0,nums.length-1);}privateTreeNodebuildTree(int[]nums,intleft,intright){// 退出条件if(left>right){returnnull;}// 得到中间值intmid=(left+right)/2;// 构建根节点TreeNoderoot=newTreeNode(nums[mid]);// 构建左子树root.left=buildTree(nums,left,mid-1);// 构建右子树root.right=buildTree(nums,mid+1,right);returnroot;}}

---

三、思路详解

3.1 为什么取中间元素就能保证平衡？

这是整道题的核心问题。我们从"平衡"的定义出发——左右子树高度差不超过 1。

假设数组长度为 n，我们取中间位置 mid，那么：

• 左子树包含mid - left个元素
• 右子树包含right - mid个元素

当 n 为奇数时，左右子树元素数完全相等；当 n 为偶数时，左右相差 1 个元素。无论哪种情况，左右子树的元素数量差距都不超过 1。

而一棵由 k 个节点构建的平衡树，其高度为 ⌊log₂k⌋ + 1。由于左右子树的节点数差距至多为 1，它们的高度差自然不会超过 1。这个性质在每一层递归中都成立，因此最终构建出的整棵树一定满足平衡条件。

3.2 为什么取中间元素就能保证 BST 性质？

BST 的性质要求：左子树所有节点值 < 根节点值 < 右子树所有节点值。

数组是升序的，这意味着：

• 下标在[left, mid - 1]范围内的元素，值都小于nums[mid]
• 下标在[mid + 1, right]范围内的元素，值都大于nums[mid]

所以我们用nums[mid]作为根节点，[left, mid - 1]去构建左子树，[mid + 1, right]去构建右子树，这个分配方式完美满足了 BST 的性质要求。每一层递归都是如此，因此整棵树一定是合法的 BST。

3.3 递归过程的拆解

把整个递归过程拆开来看，每一步做的事情非常清晰：

1. 判断当前区间是否有效：left > right时说明区间为空，没有元素可处理，返回null。这是递归的终止条件。
2. 取中间元素作为根节点：mid = (left + right) / 2，用nums[mid]创建新的树节点。
3. 递归构建左子树：在[left, mid - 1]区间上重复上述过程，返回的子树挂到root.left。
4. 递归构建右子树：在[mid + 1, right]区间上重复上述过程，返回的子树挂到root.right。
5. 返回当前根节点：整棵子树构建完毕，向上层返回。

用一个具体例子来走一遍。假设输入数组为[-10, -3, 0, 5, 9]：

第一层：区间 [0, 4]，mid = 2，根节点 = 0 ├── 左子树：区间 [0, 1]，mid = 0，根节点 = -10 │ ├── 左子树：区间 [0, -1] → null │ └── 右子树：区间 [1, 1]，mid = 1，根节点 = -3 │ ├── 左子树：区间 [1, 0] → null │ └── 右子树：区间 [2, 1] → null └── 右子树：区间 [3, 4]，mid = 3，根节点 = 5 ├── 左子树：区间 [3, 2] → null └── 右子树：区间 [4, 4]，mid = 4，根节点 = 9 ├── 左子树：区间 [4, 3] → null └── 右子树：区间 [5, 4] → null

最终构建出的树：

0 / \ -3 9 / / -10 5

每一层都严格满足：左子树值 < 根 < 右子树值，且左右高度差不超过 1。

3.4 关于 mid 的取法

代码中mid = (left + right) / 2，这是最朴素的中间值取法。在数组长度为偶数时，这种取法会偏向左边（取左中位数），比如区间[0, 3]时 mid 为 1 而非 2。

实际上，取左中位数还是右中位数都是可以的，两种取法都能构建出满足条件的平衡 BST，只是最终的树形结构略有不同。本题答案不唯一，任意一种平衡的 BST 都是合法解。

另外需要注意，(left + right) / 2在极端情况下可能存在整数溢出的风险，更安全的写法是left + (right - left) / 2，不过在本题的数据范围内一般不会触发这个问题。

3.5 复杂度分析

• 时间复杂度：O(n)。每个数组元素被访问且仅被访问一次，用于创建对应的树节点。
• 空间复杂度：O(log n)。递归调用栈的深度等于树的高度，而平衡树的高度为 log n。此外还使用了 O(n) 的空间存储构建出的树节点，但通常不计入额外空间复杂度。

---

总结：这道题的优雅之处在于，"有序数组"与"平衡 BST"之间存在一个天然桥梁——二分。利用数组的有序性，我们通过不断取中间元素来同时满足 BST 性质和平衡性质，整个过程就是一个标准的分治递归。理解了这个对应关系，代码就水到渠成了。