将有序数组转换为二叉搜索树
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡的二叉搜索树。
高度平衡二叉树是指：每个节点的左右两个子树的高度差不超过 1。数组长度在 [1, 104] 内，元素严格递增。
示例 1
示例 2
模拟答题者思考
1. 暴力直觉：枚举所有 BST 形状再验证中序是否等于 nums——组合爆炸，不可行。
2. 关键观察：有序数组就是 BST 的中序遍历；只要为每个连续子段选定一个根，左段全是左子树、右段全是右子树，BST 性质自动满足。
3. 要「高度平衡」：子树节点数尽量对半分 → 每次取区间中点作根，左右子树规模差不超过 1，树高 O(log n)。
4. 子问题同型：dfs(left, right) 只依赖区间边界，与 #105/#106 一样是分治建树，但无需哈希表——下标即中序位置。
5. 示例 1：[-10,-3,0,5,9]，根 mid=2 值 0；左 [-10,-3] 根 -3；右 [5,9] 根 9，左子 5。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
left, right | int | 定义：当前子树在有序数组 nums 上的闭区间下标维护： left > right 表示空子树，返回 null更新：根落在 mid 后，左子树 [left, mid-1]、右子树 [mid+1, right] |
mid | int | 定义：当前区间的「中点」下标，其值作为子树根节点 维护：有序数组的中序遍历即自身， nums[mid] 满足 BST 中序性质更新：常用 mid = (left + right) // 2（或偏左/偏右中点，多种答案均合法） |
root | TreeNode* | 定义：当前区间对应的 BST 根，值为 nums[mid]维护：先建根，再递归挂左、右子树（顺序任意） 更新： root.left = dfs(left, mid-1)，root.right = dfs(mid+1, right) |
落码步骤
1. 定义 dfs(left, right)：若 left > right 返回 null
2. mid = (left + right) // 2，root = TreeNode(nums[mid])
3. root.left = dfs(left, mid - 1)，root.right = dfs(mid + 1, right)
4. 返回 dfs(0, len(nums) - 1) 作为整棵树的根
代码实现
class Solution:
def sortedArrayToBST(self, nums: list[int]) -> TreeNode | None:
def dfs(left: int, right: int) -> TreeNode | None:
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = dfs(left, mid - 1)
node.right = dfs(mid + 1, right)
return node
return dfs(0, len(nums) - 1)class Solution {
TreeNode* dfs(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
auto* root = new TreeNode(nums[mid]);
root->left = dfs(nums, left, mid - 1);
root->right = dfs(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return dfs(nums, 0, (int)nums.size() - 1);
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)（递归栈 O(log n)～O(n)，共建 n 个节点）
常见坑
取根用 left 或 right 而非中点：仍可能是合法 BST，但会退化成链，不满足「高度平衡」。
右子树区间写成 [mid, right]：根已在 mid，右子树必须从 mid + 1 开始，否则会重复节点或破坏 BST。
整数溢出写法：mid = (left + right) / 2 在 C++ 里建议 left + (right - left) / 2（本题数据范围通常无碍，养成习惯）。
必测边界 Case
nums = [0] → 单节点根 0
nums = [1,3] → 根 3 左子 1，或根 1 右子 3
nums = [-10,-3,0,5,9] → 中点根 0，左右子树各再取中点
nums = [1..7] → 中点分治得近似满二叉树，高度 3