有序链表转换二叉搜索树 图解题解

这道题到底在问什么

head

-10 → -3 → 0 → 5 → 9

输出

以 0 为根的平衡 BST

要求

中序遍历能还原原链表

先想最直接的笨办法

数组取中点是 mid=(lo+hi)/2 一步到位;链表只能从头一个一个走。怎么不走两遍就找到正中间那个节点?（动画第 4 步）

最优解：一步一步想明白

1. 3中点左边的全比它小(进左子树),右边的全比它大(进右子树),数量还差不多——天然平衡。左右两段各自又是同样的小问题 → 递归。这套思路和 LC108 一模一样。
2. 4数组取中点是 mid=(lo+hi)/2 一步到位;链表只能从头一个一个走。怎么不走两遍就找到正中间那个节点?
3. 5fast 走到尽头时,slow 恰好停在正中间——因为 fast 走的路是 slow 的两倍。slow 指向的就是这一段的中点,拿它当根。
4. 6盯住两件事:上方链表里 slow/fast 怎么挪,以及下方那棵树一格一格长出节点。
5. 7slow=fast=-10(表头)处理整条链表 [-10 … 9]。slow 和 fast 一起站在表头。规则:fast 每次走两步、slow 每次走一步。
6. 8slow→-3, fast→0fast 从 -10 跳两步到 0,slow 从 -10 跳一步到 -3。fast 还没到尽头,继续。
7. 9slow→0, fast→9fast 再跳两步到末节点 9,slow 跳一步到 0。fast 到头了,循环停——此刻 slow 正停在正中间。
8. 10中点 = 0,作树根slow=0 就是整条链表的中点(标绿)。它当整棵树的根。左边 [-10,-3] 进左子树,右边 [5,9] 进右子树。
9. 110 落地,成为树根第一个节点 0 出现了,它是整棵树的根。接下来先把它的左半段 [-10,-3] 建成一棵完整子树。
10. 12slow=fast=-10递归进左半段:把链表看成只有 -10 → -3 这一截(到 0 为止,不含 0)。slow、fast 又从这段头部 -10 出发。
11. 13slow→-3, fast 越过段尾fast 想跳两步,但越过了这段的右边界(0),循环停。slow 此时停在 -3——这段的中点。
12. 14中点 = -3slow=-3 是左段中点(标绿),它将挂为根 0 的左孩子。-3 左边还剩一个 -10,右边为空。
13. 15-3 → 0 的左孩子-3 挂到了 0 的左下方(根 0 变灰表示已处理)。-3 的左边还有 [-10] 这一段,继续往下分。
14. 16slow=fast=-10再往下递归:-3 左边只剩 -10 一个节点。fast 一步都跳不出去,循环直接不进,slow 留在 -10。
15. 17中点 = -10(叶子)slow=-10(标绿)。单节点段的中点就是它自己,挂为 -3 的左孩子,左右都空,是一片叶子。
16. 18-10 → -3 的左孩子-10 落在最左下,它的左右段都空了,是叶子。到这里根 0 的整棵左子树都建好了,函数才回头去建 0 的右半段 [5,9]。
17. 19slow=fast=5现在轮到根的右半段:链表看成 5 → 9 这一截。slow、fast 从段头 5 出发。
18. 20slow→9, fast 出段fast 跳两步直接到链表末尾(null)外,循环停。slow 走一步停在 9——这段中点。
19. 21中点 = 9slow=9 是右段中点(标绿),挂为根 0 的右孩子。9 的左边还剩一个 5,右边为空。
20. 229 → 0 的右孩子9 挂到 0 的右下方。和 -3 一样,9 的左边还有 [5] 这一段要继续分。
21. 23slow=fast=5递归进 9 的左段:只剩 5 一个节点。fast 跳不出去,slow 留在 5。
22. 24中点 = 5(叶子)slow=5(标绿),挂为 9 的左孩子。它也是叶子。这是最后一个要安家的节点。
23. 255 → 9 的左孩子5 落在 9 的左下。5 个节点一格一格全长进了树里。
24. 26高度 = 3, 左右平衡 ✓树建完了:整整 3 层、左右各 2 个节点,完美平衡。每次「快慢指针取中点对半分」,树就不会长歪。
25. 27走到最左下:-10验证用「中序遍历」:一路往左走到底,最先访问最左下的 -10。合法 BST 的中序结果该是升序,我们一个节点一个节点点亮看看。
26. 28回到 -10 的父节点:-3-10 没有孩子,回到它的父节点 -3。-3 没有右孩子,左子树这一支走完,顺序是 -10 → -3,升序。
27. 29左子树走完,访问根:0左子树全部访问完,才回到根 0 点亮它。这就是中序「左→根→右」里的「根」这一步。现在去走右子树。
28. 30进入右子树最左:5进入右子树,先走到它的最左 5(9 的左孩子)。到这里序列是 -10 → -3 → 0 → 5,依旧严格升序。
29. 31最后访问右子树根:9最后访问 5 的父节点 9。完整中序:-10 → -3 → 0 → 5 → 9,和原链表分毫不差——确认它是合法 BST。
30. 32递归用「左闭右开」的区间表示一段链表:build(left, mid) 建左子树(到 mid 前为止),build(mid.next, right) 建右子树。mid 已当根用掉,左右都要排除它,否则死递归。
31. 35把 LC108 和 LC109 放一起看:同一棵树、同一套递归,唯一区别是「定位中点」的手段。想通这点,数组分治和链表分治就打通了。
32. 37右段写成 build(mid,right) → 死递归若右段误写成 build(mid, right),mid 永远被算进右段,这一段永远缩不小,同一个中点反复当根,递归停不下来直接栈溢出。右段必须从 mid.next 起。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return build(head, nullptr);
    }
    ListNode* findMid(ListNode* left, ListNode* right) {
        ListNode* slow = left; ListNode* fast = left;
        while (fast != right && fast->next != right) {
            slow = slow->next;            // 慢走一步
            fast = fast->next->next;      // 快走两步
        }
        return slow;
    }
    TreeNode* build(ListNode* left, ListNode* right) {
        if (left == right) return nullptr;    // 空段
        ListNode* mid = findMid(left, right);
        TreeNode* root = new TreeNode(mid->val);
        root->left  = build(left, mid);
        root->right = build(mid->next, right);
        return root;
    }
};

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return build(head, null);
    }
    private ListNode findMid(ListNode left, ListNode right) {
        ListNode slow = left;
        ListNode fast = left;
        while (fast != right && fast.next != right) {
            slow = slow.next;             // 慢走一步
            fast = fast.next.next;        // 快走两步
        }
        return slow;
    }
    private TreeNode build(ListNode left, ListNode right) {
        if (left == right) return null;       // 空段
        ListNode mid = findMid(left, right);
        TreeNode root = new TreeNode(mid.val);
        root.left  = build(left, mid);
        root.right = build(mid.next, right);
        return root;
    }
}

复杂度

面试官可能追问