题目概述
给你一个严格递增的整数数组 nums，要求将它转换成一棵平衡二叉搜索树（BST）。
所谓平衡，就是每个节点的左右子树高度差不超过 1。答案不唯一，只要满足 BST 性质 + 平衡即可。
核心思路：有序 + 取中间 = 天然平衡
这道题最关键的观察是：
有序数组的中间元素，天然适合做 BST 的根。
为什么？
- BST 要求左子树所有值 < 根 < 右子树所有值
- 数组已经排好序了，中间元素左边的全比它小，右边的全比它大
- 取中间做根后，左右两边的元素数量最接近相等——这就保证了平衡
所以策略就是：
- 取当前区间的中间元素做根
- 左半段递归建左子树
- 右半段递归建右子树
- 区间为空时返回
None
一句话记忆："取中间 → 递归左右"。
代码实现
class Solution:def sortedArrayToBST(self, nums):def bst(lp, rp):if lp > rp:return Nonemid = (lp + rp) // 2node = TreeNode(nums[mid])node.left = bst(lp, mid - 1)node.right = bst(mid + 1, rp)return nodereturn bst(0, len(nums) - 1)
逐行拆解
1. 递归函数签名：bst(lp, rp)
lp：当前子数组的左边界（闭区间）rp：当前子数组的右边界（闭区间）- 这两个参数控制"当前递归看到的是数组的哪一段"
2. 终止条件：if lp > rp: return None
当左边界超过右边界，说明当前区间已经没有元素了，返回空节点。
3. 取中间：mid = (lp + rp) // 2
找到当前区间的中间位置。Python 不用担心整数溢出，直接相加除以 2 即可。
小知识：在 C++ / Java 中，更安全的写法是
mid = lp + (rp - lp) // 2，避免lp + rp溢出。
4. 创建当前节点：node = TreeNode(nums[mid])
中间元素作为当前子树的根节点。
5. 递归建左子树：node.left = bst(lp, mid - 1)
左半段 [lp, mid-1] 的所有元素都比 nums[mid] 小，递归构建左子树。
6. 递归建右子树：node.right = bst(mid + 1, rp)
右半段 [mid+1, rp] 的所有元素都比 nums[mid] 大，递归构建右子树。
7. 返回当前节点：return node
把构建好的子树根节点返回给上一层，让父节点接上。
手动模拟
以 nums = [-10, -3, 0, 5, 9] 为例：
第 1 层：bst(0, 4)mid = 2 → 根节点 = 0左子树 = bst(0, 1)右子树 = bst(3, 4)第 2 层（左）：bst(0, 1)mid = 0 → 根节点 = -10左子树 = bst(0, -1) → None右子树 = bst(1, 1)第 3 层：bst(1, 1)mid = 1 → 根节点 = -3左子树 = None，右子树 = None第 2 层（右）：bst(3, 4)mid = 3 → 根节点 = 5左子树 = bst(3, 2) → None右子树 = bst(4, 4)第 3 层：bst(4, 4)mid = 4 → 根节点 = 9左子树 = None，右子树 = None
最终构建出的树：
0/ \-10 5\ \-3 9
中序遍历：[-10, -3, 0, 5, 9]，和原数组一致，BST 性质成立，左右高度差不超过 1，平衡性成立。
复杂度分析
| 复杂度 | 说明 | |
|---|---|---|
| 时间 | O(n) | 每个元素恰好被访问一次，创建一个节点 |
| 空间 | O(log n) | 递归栈深度等于树的高度，平衡树高度为 log n |
为什么不能从头开始一个个插入？
很多初学者会想：既然要建 BST，那我一个个把元素插进去不就行了？
问题是：如果数组是有序的，从头到尾逐个插入会退化成一条链——每个新节点都成了上一个节点的右孩子，树的高度变成 n，根本不平衡。
所以这题的关键不是"怎么插入"，而是"怎么选根"。每次选中间元素做根，是保证平衡的核心。
这题的本质：分治
这道题其实是分治思想的经典应用：
- 分：把有序数组从中间一分为二
- 治：左半段递归建左子树，右半段递归建右子树
- 合：中间元素做根，把左右子树接上
和归并排序、快速排序的思路一脉相承。掌握了"取中间 → 递归左右"这个模式，后面遇到类似的分治建树题（比如从前序/中序遍历构造二叉树）也会更顺。
总结
| 要点 | 内容 |
|---|---|
| 核心思路 | 有序数组取中间做根，左右递归建子树 |
| 为什么平衡 | 每次取中间，左右元素数量最接近相等 |
| 递归三要素 | 参数 = 区间边界，终止 = 空区间，返回 = 当前子树根 |
| 本质 | 分治：分 → 治 → 合 |
这题是递归建树的入门题，也是理解分治思想的好素材。把"取中间当根 → 递归左右"这个模式吃透，后面很多树的构造题都不会再发怵。