有序链表转换二叉搜索树
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个单链表的头节点 head，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
高度平衡二叉树指每个节点左右子树高度差不超过 1。节点数 [0, 2×104]，值域 [-105, 105]。
示例 1
示例 2
模拟答题者思考
1. 与 #108 相同：升序序列就是 BST 的中序；每次取区间中点作根，左段进左子树、右段进右子树，即得高度平衡 BST。
2. 链表不能像数组一样 O(1) 按下标取「中点值」：暴力每层用快慢指针找子链表中点，可行但每层 O(n)，总复杂度 O(n log n)。
3. 找重复：建树逻辑与 #108 完全一致，瓶颈只是「如何稳定拿到中点元素」。
4. 实用落码：先 O(n) 扫链表写入数组 vals，再对 vals 跑 #108 的分治 dfs(left, right)，总时间 O(n)、实现清晰。
5. 进阶：用全局 cur 指针按中序顺序「同步」扫链表并建树，可省数组、仍 O(n) 时间（先建左子树 → 取 cur 作根 → 建右子树）。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
vals | list[int] | 定义：升序链表各节点值按遍历顺序存入的数组（等价于 BST 的中序序列） 维护：建树前一次性扫完链表，之后只读 更新：沿 head 走链表，vals.append(node.val) 直至 null |
left, right | int | 定义：当前子树在 vals 上的闭区间下标维护： left > right 表示空子树更新：根在 mid 后，左子 [left, mid-1]、右子 [mid+1, right] |
mid | int | 定义：当前区间中点下标，值 vals[mid] 作为子树根维护：保证左右子树规模大致对半，树高 O(log n) 更新： mid = (left + right) // 2 |
cur（可选写法） | ListNode* | 定义：中序模拟时「下一个待写入 BST 的链表节点」 维护：先递归建左子树会扫过左段链表，再取 cur.val 作根并 cur = cur.next更新：仅在中序建树写法中使用，与 vals[mid] 角色对应 |
落码步骤
1. 若 head == null 返回 null；否则遍历链表填入 vals
2. 定义 dfs(left, right)：left > right 返回 null
3. mid = (left + right) // 2，root = TreeNode(vals[mid])
4. root.left = dfs(left, mid - 1)，root.right = dfs(mid + 1, right)
5. 返回 dfs(0, len(vals) - 1)
代码实现
class Solution:
def sortedListToBST(self, head: ListNode | None) -> TreeNode | None:
vals: list[int] = []
while head:
vals.append(head.val)
head = head.next
def dfs(left: int, right: int) -> TreeNode | None:
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(vals[mid])
node.left = dfs(left, mid - 1)
node.right = dfs(mid + 1, right)
return node
return dfs(0, len(vals) - 1) if vals else Noneclass Solution {
TreeNode* dfs(vector<int>& vals, int left, int right) {
if (left > right) return nullptr;
int mid = left + (right - left) / 2;
auto* root = new TreeNode(vals[mid]);
root->left = dfs(vals, left, mid - 1);
root->right = dfs(vals, mid + 1, right);
return root;
}
public:
TreeNode* sortedListToBST(ListNode* head) {
vector<int> vals;
for (auto* p = head; p; p = p->next) vals.push_back(p->val);
if (vals.empty()) return nullptr;
return dfs(vals, 0, (int)vals.size() - 1);
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)（数组/节点存储；递归栈 O(log n)）
常见坑
忘记空链表：未判 head == null 时 dfs(0, -1) 虽能返回 null，但显式处理更清晰。
右子树区间写成 [mid, right]：根已在 mid，右子必须从 mid + 1 开始，否则会重复值或破坏 BST。
每层快慢指针找中点却未截断链表：指针易混；若坚持链表分治，需明确子区间起止节点或改用中序 cur 写法。
必测边界 Case
head = [] → null
head = [0] → 单节点根 0
[-10,-3,0,5,9] → vals 同序，中点根 0
head = [1,3] → 根 3 左子 1 或根 1 右子 3（均合法）