有序链表转换二叉搜索树

怎样从“升序链表 -10→-3→0→5→9 转高度平衡 BST。”推导出 BST · 链表版 LC108，并证明每次状态变化都不会漏掉答案？

中心结论：主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。

将链表转化为高度平衡的二叉搜索树。高度平衡的定义：每个结点的 2 个子结点的深度不能相差超过 1 。

在本站主例中，升序链表 -10→-3→0→5→9 转高度平衡 BST。

算法最终需要得到或观察：高度平衡 BST，中序仍为升序。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 slow/fast、prev.Next=nil、递归栈。
3. 3转移每一步按照 主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。
4. 4收尾读取 高度平衡 BST，中序仍为升序。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：slow/fast、prev.Next=nil、递归栈。

思路比较简单，依次把链表的中间点作为根结点，类似二分的思想，递归排列所有结点即可。

主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。

执行过程中持续维护：slow/fast、prev.Next=nil、递归栈。

正确性依赖以下不变量：链表版 LC108：不能 O(1) 取 mid，每层扫描找中点。；BST 中序遍历 = 升序链表顺序。

面试时可以压缩为：快慢找中点断链递归 O(n log n)；要 O(n) 用中序模拟。

落到当前题，执行机制可以压缩为：主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入升序链表 -10→-3→0→5→9 转高度平衡 BST。 因为：主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。
2. 2BFS 队列层序根入队。 因为：FIFO 保证同层顺序。
3. 3出队访问 -3访问并把左右孩子入队。 因为：size 快照划分层界。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5出队访问 0访问并把左右孩子入队。 因为：size 快照划分层界。
6. 6出队访问 5访问并把左右孩子入队。 因为：size 快照划分层界。
7. 7层序: [-10] | [-3,0] | [5,9]队列为空。 因为：O(n) BFS。
8. 8收尾与复杂度高度平衡 BST，中序仍为升序。 因为：时间 O(n log n) · 空间 O(log n)。主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func sortedListToBST(head *ListNode) *TreeNode {
	if head == nil {
		return nil
	}
	if head != nil && head.Next == nil {
		return &TreeNode{Val: head.Val, Left: nil, Right: nil}
	}
	middleNode, preNode := middleNodeAndPreNode(head)
	if preNode != nil {
		preNode.Next = nil
	}
	if middleNode == head {
		head = nil
	}
	return &TreeNode{Val: middleNode.Val, Left: sortedListToBST(head), Right: sortedListToBST(middleNode.Next)}
}

func middleNodeAndPreNode(head *ListNode) (middle *ListNode, pre *ListNode) {
	if head == nil || head.Next == nil {
		return nil, head
	}
	p1 := head
	p2 := head
	for p2.Next != nil && p2.Next.Next != nil {
		pre = p1
		p1 = p1.Next
		p2 = p2.Next.Next
	}
	return p1, pre
}

func main() {
    // 1. 主例
    //    输入：mode="level-order", values=[-10,-3,0,5,9]
    //    期望：高度平衡 BST，中序仍为升序。
    //
    // 2. 失败 / 未命中
    //    检查：忘记 prev.next=nil 会死循环；勿把快慢分治误写成 O(n)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC108 数组转 BST；LC148 排序链表
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意升序链表 -10→-3→0→5→9 转高度平衡 BST。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化主线：快慢指针找中点、prev断链、递归左右 O(n log n)；进阶：中序模拟 O(n)。
4. 4证明链表版 LC108：不能 O(1) 取 mid，每层扫描找中点。；BST 中序遍历 = 升序链表顺序。
5. 5复杂度时间 O(n log n)，空间 O(log n)