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

一、题目条件分析

将有序数组转换为二叉搜索树题目

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

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

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

二、思路概览与代码

思路概览

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int left, int right) {
        // 退出条件
        if (left > right) {
            return null;
        }
        // 得到中间值
        int mid = (left + right) / 2;
        // 构建根节点
        TreeNode root = new TreeNode(nums[mid]);
        // 构建左子树
        root.left = buildTree(nums, left, mid - 1);
        // 构建右子树
        root.right = buildTree(nums, mid + 1, right);
        return root;
    }
}

三、思路详解

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]：

1
2
3
4
5
6
7
8
9
10
11
第一层：区间 [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

最终构建出的树：

1
2
3
4
5
      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 性质和平衡性质，整个过程就是一个标准的分治递归。理解了这个对应关系，代码就水到渠成了。