108. 将有序数组转换为二叉搜索树#

生活隐喻：图书馆的二分法则#

想象你是一名图书管理员，面对刚到的百科全书，它们按序号整齐排列。你需要设计一个检索系统：当读者询问任意编号时，都能以最少的步骤找到目标。你会如何摆放这些书籍？

聪明的管理员会将中间卷放在最显眼位置，左半部分交给左侧书架，右半部分交给右侧书架——这正是二叉搜索树的智慧。而今天我们要解决的，正是这种思维在算法世界的完美映射。

问题描述#

题目目标#

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树并返回根节点。

示例 1#

输入： nums = [-10,-3,0,5,9] 输出： [0,-3,9,-10,null,5] 二叉树示意：

     0 
    /  \
   -3  9
 /    /
-10   5

说明： 答案不唯一，任意一棵平衡 BST 均可

补充说明#

• 二叉树通常使用层序数组表示，null 表示该位置没有节点。

问题本质#

LeetCode第108题”将有序数组转换为二叉搜索树”要求：给定一个元素按升序排列的整数数组，将其转换为高度平衡的二叉搜索树（即每个节点的左右两个子树的高度差绝对值不超过1）。

示例： 输入：[-10,-3,0,5,9] 可能的输出（不唯一）：

      0
     / \
   -3   9
   /   /
 -10  5

直觉陷阱：线性思维的局限#

面对有序数组，新手常陷入两种极端：

1. 直接构建链式结构（始终选择最右/左节点），导致退化成链表
2. 过度追求完美平衡，陷入复杂的旋转调整

这两种方式都违背了”高度平衡”的本质要求——我们需要的是结构性平衡，而非绝对对称。

破局密钥：分治的二分美学#

真正的解法蕴含在数组的有序性中。就像折半查找的原理，我们可以通过递归的二分策略，自然生长出平衡的树结构。

算法三要素#

1. 根的选择：始终选取当前区间的中间元素作为根节点
2. 左右子树：左区间构建左子树，右区间构建右子树
3. 递归终止：当区间为空时返回null

动态推演#

以示例[-10,-3,0,5,9]为例：

1. 第一层递归：选择索引2（0）为根
   • 左区间[-10,-3]，右区间[5,9]
2. 左子树递归：选择索引0（-10）为根
   • 左区间空，右区间[-3]
3. 右子树递归：选择索引3（5）为根
   • 左区间空，右区间[9]

最终形成的树结构天然满足高度平衡的要求。

时空契约#

• 时间复杂度：O(n)。每个元素恰好被访问一次
• 空间复杂度：O(log n)。递归栈的深度由树高决定

代码圣殿#

public TreeNode sortedArrayToBST(int[] nums) {
    // 从整个数组区间 [0, n-1] 开始递归构建平衡 BST
    return buildTree(nums, 0, nums.length - 1);
}

private TreeNode buildTree(int[] nums, int left, int right) {
    // 递归终止条件：区间为空（left 越过 right）时返回空节点
    if (left > right) return null;

    // 计算中点索引：写成 left + (right - left) / 2 可避免整数溢出
    int mid = left + (right - left) / 2;

    // 用中间元素创建当前子树根节点（保证左右规模尽量平衡）
    TreeNode root = new TreeNode(nums[mid]);
    // 递归构建左子树：使用中点左边区间 [left, mid-1]
    root.left = buildTree(nums, left, mid - 1);
    // 递归构建右子树：使用中点右边区间 [mid+1, right]
    root.right = buildTree(nums, mid + 1, right);

    // 返回当前构建完成的子树根节点
    return root;
}

关键细节：

1. 使用左右指针界定区间，避免数组拷贝
2. 中间位置计算采用left + (right - left)/2防止整数溢出
3. 递归终止条件left > right确保空区间正确处理

方法哲学：分治的宇宙观#

这种解法体现了计算机科学中最优雅的思想之一——分而治之：

1. 分解：将大问题拆分为相似的小问题
2. 解决：递归处理子问题
3. 合并：组合子树形成完整解决方案

这种思维模式可推广到：

• 归并排序中的数组分割
• 快速排序中的分区操作
• 棋盘覆盖问题的递归求解

思维跃迁#

通过此题我们领悟到：

1. 有序蕴含结构：看似线性的序列中隐藏着树形拓扑
2. 平衡源于对称：二分法天然保证树的结构平衡
3. 递归即自相似：每个子树都是原问题的微型镜像

拓展训练#

尝试用类似思路解决这些问题：

1. 有序链表转换二叉搜索树（LeetCode 109）
2. 前序+中序序列构建二叉树（LeetCode 105）
3. 将二叉搜索树转为平衡树（LeetCode 1382）