题目描述
思路解析动画文字版
中点左边的全比它小(进左子树),右边的全比它大(进右子树),数量还差不多——天然平衡。左右两段各自又是同样的小问题 → 递归。这套思路和 LC108 一模一样。
数组取中点是 mid=(lo+hi)/2 一步到位;链表只能从头一个一个走。怎么不走两遍就找到正中间那个节点?
fast 走到尽头时,slow 恰好停在正中间——因为 fast 走的路是 slow 的两倍。slow 指向的就是这一段的中点,拿它当根。
盯住两件事:上方链表里 slow/fast 怎么挪,以及下方那棵树一格一格长出节点。
整段找中点 · 起步：处理整条链表 [-10 … 9]。slow 和 fast 一起站在表头。规则:fast 每次走两步、slow 每次走一步。
整段找中点 · 走一轮：fast 从 -10 跳两步到 0,slow 从 -10 跳一步到 -3。fast 还没到尽头,继续。
整段找中点 · 再走一轮：fast 再跳两步到末节点 9,slow 跳一步到 0。fast 到头了,循环停——此刻 slow 正停在正中间。
中点确定 · slow=0：slow=0 就是整条链表的中点(标绿)。它当整棵树的根。左边 [-10,-3] 进左子树,右边 [5,9] 进右子树。
根诞生 · 0：第一个节点 0 出现了,它是整棵树的根。接下来先把它的左半段 [-10,-3] 建成一棵完整子树。
左段 [-10,-3] · 找中点起步：递归进左半段:把链表看成只有 -10 → -3 这一截(到 0 为止,不含 0)。slow、fast 又从这段头部 -10 出发。
左段 · fast 走一轮就到边界：fast 想跳两步,但越过了这段的右边界(0),循环停。slow 此时停在 -3——这段的中点。
左段中点 · slow=-3：slow=-3 是左段中点(标绿),它将挂为根 0 的左孩子。-3 左边还剩一个 -10,右边为空。
挂左孩子 · -3：-3 挂到了 0 的左下方(根 0 变灰表示已处理)。-3 的左边还有 [-10] 这一段,继续往下分。
-3 的左段 [-10] · 单节点：再往下递归:-3 左边只剩 -10 一个节点。fast 一步都跳不出去,循环直接不进,slow 留在 -10。
-3 的左段中点 · slow=-10：slow=-10(标绿)。单节点段的中点就是它自己,挂为 -3 的左孩子,左右都空,是一片叶子。
挂叶子 · -10：-10 落在最左下,它的左右段都空了,是叶子。到这里根 0 的整棵左子树都建好了,函数才回头去建 0 的右半段 [5,9]。
右段 [5,9] · 找中点起步：现在轮到根的右半段:链表看成 5 → 9 这一截。slow、fast 从段头 5 出发。
右段 · fast 走一轮到尽头：fast 跳两步直接到链表末尾(null)外,循环停。slow 走一步停在 9——这段中点。
右段中点 · slow=9：slow=9 是右段中点(标绿),挂为根 0 的右孩子。9 的左边还剩一个 5,右边为空。
挂右孩子 · 9：9 挂到 0 的右下方。和 -3 一样,9 的左边还有 [5] 这一段要继续分。
9 的左段 [5] · 单节点：递归进 9 的左段:只剩 5 一个节点。fast 跳不出去,slow 留在 5。
9 的左段中点 · slow=5：slow=5(标绿),挂为 9 的左孩子。它也是叶子。这是最后一个要安家的节点。
挂叶子 · 5：5 落在 9 的左下。5 个节点一格一格全长进了树里。
建树完成：树建完了:整整 3 层、左右各 2 个节点,完美平衡。每次「快慢指针取中点对半分」,树就不会长歪。
中序遍历验证 · 访问 -10：验证用「中序遍历」:一路往左走到底,最先访问最左下的 -10。合法 BST 的中序结果该是升序,我们一个节点一个节点点亮看看。
中序遍历验证 · 访问 -3：-10 没有孩子,回到它的父节点 -3。-3 没有右孩子,左子树这一支走完,顺序是 -10 → -3,升序。
中序遍历验证 · 访问根 0：左子树全部访问完,才回到根 0 点亮它。这就是中序「左→根→右」里的「根」这一步。现在去走右子树。
中序遍历验证 · 访问 5：进入右子树,先走到它的最左 5(9 的左孩子)。到这里序列是 -10 → -3 → 0 → 5,依旧严格升序。
中序遍历验证 · 访问 9：最后访问 5 的父节点 9。完整中序:-10 → -3 → 0 → 5 → 9,和原链表分毫不差——确认它是合法 BST。
递归用「左闭右开」的区间表示一段链表:build(left, mid) 建左子树(到 mid 前为止),build(mid.next, right) 建右子树。mid 已当根用掉,左右都要排除它,否则死递归。
把 LC108 和 LC109 放一起看:同一棵树、同一套递归,唯一区别是「定位中点」的手段。想通这点,数组分治和链表分治就打通了。
雷区实演 · 右段含 mid：若右段误写成 build(mid, right),mid 永远被算进右段,这一段永远缩不小,同一个中点反复当根,递归停不下来直接栈溢出。右段必须从 mid.next 起。
边界三连：空、单节点、两节点都能被「左闭右开 + 快慢指针」统一处理,不需要特判。
面试追问：「与 LC108 的区别」「能否 O(n)」「区间为何半开」是这题面试常被追的三点。
参考代码
class Solution: def sortedListToBST(self, head): def findMid(left, right): slow = fast = left while fast != right and fast.next != right: slow = slow.next # 慢走一步 fast = fast.next.next # 快走两步 return slow # 停在中点 def build(left, right): if left == right: # 左闭右开,空段 return None mid = findMid(left, right) root = TreeNode(mid.val) # 中点当根 root.left = build(left, mid) # 左段 [left,mid) root.right = build(mid.next, right) # 右段 (mid,right) return root return build(head, None)复杂度
- 时间复杂度：O(n log n)，每层找中点要扫一遍该层的所有节点,共 O(n);递归 log n 层 → O(n log n)
- 空间复杂度：O(log n)，树高 O(log n),递归栈最深 O(log n)(不计输出树本身)
易错点
面试追问把动画讲成自己的话
追问和 LC108 数组版的唯一区别是什么?
追问能不能优化到 O(n)?
追问为什么用左闭右开区间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
路径总和 II
LeetCode 113 · 中等 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题