LeetCode 109. 有序链表转换二叉搜索树
目录
题目描述
题意分析
输入是一条按升序排好的单链表，要求用它的全部元素构造一棵高度平衡的二叉搜索树，返回树根。题目还说明答案不唯一，只要满足条件的任意一棵都算对。
三个词各自给出信号。「有序」加上「二叉搜索树」意味着中序遍历的结果被完全确定了——BST 的中序是升序，而链表本身就是升序，所以链表的顺序就是目标树的中序序列，剩下的自由度只在于「谁当根」。「高度平衡」在本题里的定义是每个节点的左右子树高度差不超过 1，最省事的满足办法是每次都取当前这段元素的中间位置当根，这样左右两边的元素个数最多差 1。「链表」则是最大的限制：只能从头顺序访问，取第 $i$ 个元素要走 $i$ 步，没有 $O(1)$ 随机访问。
边界情况：空链表返回空；只有一个节点时返回单节点树；两个节点时无论把哪个当根都平衡，这也印证了「答案不唯一」。链表长度上限是 $2 \times 10^4$，如果写成递归，要顺带估一下栈深会不会出问题。
解法：按中序顺序构造平衡 BST
核心思路
快慢指针可以反复找链表中点，但每层都会重新扫描子链表，总时间为 $O(n \log n)$；转成数组能做到 $O(n)$ 时间，却需要 $O(n)$ 额外空间。更优的做法是利用「有序链表顺序就是 BST 中序序列」，顺序消费链表并同时构造树。
区间
[left, right]只决定子树形状：取中点后，左右元素数量最多相差 1。节点值由全局游标current提供，构造顺序严格为「左子树 → 根 → 右子树」，与中序遍历一致，所以链表只需从头到尾移动一次。不变量是：进入
build(left, right)时，current指向下标left的链表节点；返回时指向right + 1。左子树返回后游标恰在mid，根消费它，再由右子树消费余下节点。对区间长度归纳即可证明中序结果等于原链表；每层左右规模最多差 1，因此树高度平衡。
解题步骤
- 遍历链表得到长度 $n$，再把
current初始化为head。- 调用闭区间
build(0, n - 1)；当left > right时返回空节点。- 计算中点，先递归构造左子树，使游标移动到本区间的中间节点。
- 用
current.val创建根并推进游标，再递归构造右子树。- 挂接左右子树并返回根节点。
例如
[-10,-3,0,5,9]的根区间中点为 2。先递归消费-10,-3构造左子树，此时游标正指向0，用它建根；随后消费5,9构造右子树。最终中序序列与链表完全一致。
代码实现
class Solution {
private ListNode current;
public TreeNode sortedListToBST(ListNode head) {
current = head;
int length = 0;
for (ListNode node = head; node != null; node = node.next) {
length++;
}
return build(0, length - 1);
}
private TreeNode build(int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode leftChild = build(left, mid - 1);
// 中序位置对应当前链表节点。
TreeNode root = new TreeNode(current.val);
current = current.next;
root.left = leftChild;
root.right = build(mid + 1, right);
return root;
}
}
func sortedListToBST(head *ListNode) *TreeNode {
length := 0
for node := head; node != nil; node = node.Next {
length++
}
current := head
var build func(int, int) *TreeNode
build = func(left int, right int) *TreeNode {
if left > right {
return nil
}
mid := left + (right-left)/2
leftChild := build(left, mid-1)
// 构造顺序与 BST 中序遍历顺序一致。
root := &TreeNode{Val: current.Val}
current = current.Next
root.Left = leftChild
root.Right = build(mid+1, right)
return root
}
return build(0, length-1)
}
复杂度分析
- 时间复杂度：$O(n)$。统计长度和建树各线性遍历一次，每个链表节点只被消费一次。
- 空间复杂度：$O(\log n)$。不计结果树，只使用平衡递归产生的调用栈。
关键点总结
- 有序链表的顺序就是目标 BST 的中序序列，因此构造顺序必须严格是「左子树 → 根 → 右子树」，任何打乱这个顺序的写法都会让值错位。
- 下标区间只用来决定树的形状（谁当根、左右各几个），取值一律来自游标，两者职责分离，就不需要真的把链表搬进数组。
- 游标的进出不变量（进函数时指向
left，出函数时指向right + 1）是整个解法正确性的唯一依据，写代码前先把它说清楚。- 面试时可先说明快慢指针方案的 $O(n \log n)$ 瓶颈，再用中序游标优化到 $O(n)$，体现优化依据而不只是背模板。
易错点总结
- 错误写法：把「新建根」提到「建左子树」之前，写成
TreeNode root = new TreeNode(current.val); root.left = build(left, mid - 1);。用[-10, -3, 0, 5, 9]走：根抢先拿走了-10，左子树只能拿到-3和0，中序遍历结果不再是升序，BST 性质直接被破坏。- 错误写法：把统计长度和游标混用同一个变量，例如先
current = head，再用current去做长度遍历。统计结束时current已经走到链表末尾的空，build第一次取current.val就空指针异常。- 错误写法：把游标当作普通参数按值传递。子调用推进后的新位置无法传回父调用，左右子树会重复消费节点。
- 错误写法：递归出口写成
if (left >= right) return null;。用[-10, -3]走：build(0, 1)内部的右半build(1, 1)因为1 >= 1直接返回空，节点-3被丢掉，最终树里只剩一个节点。- 错误写法：入口调用写成
build(0, length)，把闭区间当成半开区间用。区间多出一个位置，current走到空之后仍被取值，抛出空指针异常。- 错误写法：图省事直接拿链表头当根、其余全部挂到右子树上。用
[-10, -3, 0, 5, 9]走：得到一条向右倾斜的链，高度为 5，虽然中序仍是升序、BST 性质成立，但完全不满足「高度平衡」，判题不通过。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 108. 将有序数组转换为二叉搜索树 | 简单 | 有序数组下标取中点建树 |
| 105. 从前序与中序遍历序列构造二叉树 | 中等 | 前序定根、中序切分左右子树 |
| 106. 从中序与后序遍历序列构造二叉树 | 中等 | 后序末位定根，注意递归顺序反转 |
| 889. 从前序与后序遍历序列构造二叉树 | 中等 | 信息不足导致答案不唯一 |
| 110. 平衡二叉树 | 简单 | 反向判定一棵树是否高度平衡 |
| 面试题 04.02. 最小高度树 | 简单 | 同一构造目标换成最小高度的表述 |