LeetCode 108 有序数组转平衡二叉搜索树：递归建树模板一次搞懂
刷二叉树的时候，经常会遇到两类题：
- 给你一棵树，让你遍历、计算、修改；
- 给你一组数据，让你从零构建一棵树。
LeetCode 108《将有序数组转换为二叉搜索树》就是第二类题目的经典代表。
这道题不仅考察二叉搜索树（BST）的性质，更重要的是让我们掌握一个非常重要的思想：
如何利用递归和分治，从零构造一棵树。
一、题目描述
给定一个升序排列的整数数组 nums。
要求：
例如：
nums = [–10,–3,0,5,9]
可能构造出：
0
/ \\
-3 9
/ /
-10 5
二、先理解两个关键概念
什么是二叉搜索树（BST）
二叉搜索树满足：
左子树所有节点值 < 根节点值 < 右子树所有节点值
例如：
4
/ \\
2 6
满足：
2 < 4 < 6
BST 有一个重要性质：
中序遍历结果一定是升序序列。
即：
左 → 根 → 右
得到：
2 4 6
刚好有序。
而题目给我们的数组本身就是升序的，因此它天然符合 BST 的中序遍历结果。
什么是平衡二叉树
平衡二叉树要求：
任意节点左右子树高度差不超过 1
例如：
3
/ \\
1 5
左右高度相同。
属于平衡树。
而下面这种：
1
\\
2
\\
3
明显向一边倾斜。
不属于平衡树。
三、核心思路：为什么一定要选中间节点？
很多同学看到题目后会想到：
把第一个元素当根
例如：
[1,2,3,4,5]
构造：
1
\\
2
\\
3
\\
4
\\
5
虽然满足 BST。
但完全失去了平衡。
为了保证左右子树高度接近。
最合理的选择就是：
每次都选择区间中间位置作为根节点。
例如：
[1,2,3,4,5]
中间元素：
3
作为根：
3
左边：
[1,2]
构造左子树。
右边：
[4,5]
构造右子树。
这样左右节点数量最多只差一个。
天然接近平衡。
四、分治思想
这道题本质上是一个经典的分治问题。
大问题：
用整个数组构造 BST
拆成两个小问题：
用左半部分构造左子树
用右半部分构造右子树
而左右子树又可以继续递归拆分。
因此非常适合递归解决。
五、递归函数设计
定义函数：
build(left, right)
含义：
利用 nums[left:right] 这一段区间
构造一棵平衡BST
返回根节点
递归终止条件
如果区间没有元素：
left > right
说明已经无法继续构造节点。
直接返回：
None
if left > right:
return None
找到中间节点
mid = (left + right) // 2
例如：
left = 0
right = 4
得到：
mid = 2
对应：
nums[2]
作为根节点。
创建根节点
root = TreeNode(nums[mid])
例如：
nums[mid] = 3
创建：
3
递归构造左右子树
左半部分：
left_root = build(left, mid – 1)
右半部分：
right_root = build(mid + 1, right)
得到左右子树后：
root.left = left_root
root.right = right_root
最后返回当前根节点：
return root
六、完整代码
from typing import List, Optional
class Solution:
def sortedArrayToBST(self, nums: List[int]) –> Optional[TreeNode]:
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)
七、完整执行过程
输入：
nums = [1,2,3,4,5]
第一次递归：
build(0,4)
中点：
mid = 2
创建根节点：
3
构造左子树：
build(0,1)
中点：
mid = 0
创建：
1
继续递归：
build(1,1)
创建：
2
得到：
1
\\
2
构造右子树：
build(3,4)
中点：
mid = 3
创建：
4
继续递归：
build(4,4)
创建：
5
得到：
4
\\
5
最终拼接：
3
/ \\
1 4
\\ \\
2 5
八、时间复杂度分析
时间复杂度
每个节点只会被创建一次。
因此：
O(n)
其中：
n = len(nums)
空间复杂度
递归深度取决于树高度。
平衡树高度：
O(log n)
因此递归栈空间：
O(log n)
九、这道题真正想考什么？
很多人以为这是一道 BST 题。
实际上面试官更想考察的是：
1. 分治思想
把大问题拆成两个完全相同的小问题。
2. 递归建树
会不会设计：
build(left,right)
这样的递归函数。
3. 区间递归
数组题中经常出现：
left
right
mid
这一套区间递归模板。
十、递归建树模板总结
以后看到：
- 有序数组构造 BST
- 前序+中序构造二叉树
- 中序+后序构造二叉树
- 最大二叉树
本质都是：
def build(...):
if 终止条件:
return None
找到根节点
root = TreeNode(...)
root.left = build(...)
root.right = build(...)
return root
记住这个模板。
后面的建树题基本都是在此基础上变形。
对于二叉树专题来说，这道题最大的收获不是答案，而是掌握：
递归不仅能遍历树，也能从零开始构造一棵树。
