108. 将有序数组转换为二叉搜索树 (Easy)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个整数数组 nums，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 的二叉搜索树。
高度平衡 二叉树是指：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也是正确答案。
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡的 BST。
提示：
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums按 严格递增 顺序排列
题目详细分析
- 数据范围含义： 最长 10000 个元素，值范围 [-10000, 10000]，递归深度约 log₂(10000) ≈ 14，完全不用担心栈溢出。因为每次取中点分割数组，树高天然为 O(log n)。
- 输入输出特征： 输入是升序整数数组，输出是树的根节点。数组是严格递增的（无重复值）。
- 边界条件：
nums至少有一个元素（题目保证长度 ≥ 1）。 - 核心约束： 必须构建 高度平衡 的 BST。这意味着不能简单地把数组串成链状，而要用二分的方式构建。
- 隐藏条件： 只要平衡即可，答案可能不唯一（因为中点取法可能左偏或右偏）。
小白版直白理解
就像搭人梯拍照——要让最高的站在中间，个子矮的往两边依次排开，这样才能让整个队伍两边高度尽量平衡。有序数组的中间值就是树的根，左边的（更小的）全去左子树，右边的（更大的）全去右子树，左右子树用同样的方式继续搭建。
解题思路
思路一：递归取中点（推荐）
核心思想： 每次取数组的中间元素作为当前子树的根，左半部分递归构建左子树，右半部分递归构建右子树。由于每次都取中点，左右子树的元素数量最多相差 1，树的高度自然平衡。
为什么这样就能保证平衡？ 因为每层递归都将数组对半分割，左右子树的节点数最多差 1，递归深度为 O(log n)。每个节点的左右子树大小基本相等，自然平衡。
def sortedArrayToBST(nums):
def build(left, right):
# 终止条件：区间为空
if left > right:
return None
# 取中点作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
# 递归构建左右子树
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(nums) - 1)思路二：迭代法（栈模拟）
用栈模拟递归过程，避免系统递归调用。适合对递归深度有严格限制的场景。
def sortedArrayToBST(nums):
if not nums:
return None
# 栈中存储 (节点, 左边界, 右边界, 是否已处理左右)
# 使用一个虚拟根节点
mid = (0 + len(nums) - 1) // 2
root = TreeNode(nums[mid])
stack = [(root, 0, len(nums) - 1, False)]
while stack:
node, l, r, processed = stack.pop()
mid = (l + r) // 2
if not processed:
# 第一次处理：先入栈（后序处理），再处理左右
stack.append((node, l, r, True))
# 处理左子树
if l <= mid - 1:
left_mid = (l + mid - 1) // 2
node.left = TreeNode(nums[left_mid])
stack.append((node.left, l, mid - 1, False))
# 处理右子树
if mid + 1 <= r:
right_mid = (mid + 1 + r) // 2
node.right = TreeNode(nums[right_mid])
stack.append((node.right, mid + 1, r, False))
return root易错点
- 终止条件是
left > right而不是left >= right： 当 left == right 时，还有一个元素需要构建节点。>才是区间为空。 - 中点计算溢出问题： 在 Java/C++ 中
(left + right) // 2可能溢出，更安全的写法是left + (right - left) // 2。Python 中无此问题。 - 严格递增数组，无需处理重复值： 题目保证严格递增，但如果是「非严格递增」，BST 的左右分配就需要考虑重复值策略。
- 取整方向：
(left + right) // 2是向下取整，会偏左。如果总想偏右可以用(left + right + 1) // 2。
框架提炼
分治法 + 递归构建二叉搜索树模板：
def build(l, r):
if l > r:
return None
mid = (l + r) // 2 # 取中点
root = TreeNode(nums[mid]) # 构建根
root.left = build(l, mid - 1) # 左半部分
root.right = build(mid + 1, r) # 右半部分
return root这个「取中点、分左右」的模式是「有序数组/链表 → 平衡 BST」的标准解法，也适用于将有序链表转换为 BST（只是找中点的方式变为快慢指针）。
关联题目
- 105-从前序与中序遍历构造二叉树 — 更通用的二叉树构建问题，不局限于 BST，但需要两种遍历结果配合。
- 98-验证二叉搜索树 — 构建出 BST 后需要验证其合法性，与本题形成「构建→验证」闭环。
- 109-有序链表转换二叉搜索树 — 链表版，用快慢指针找中点替代数组的随机访问。