LeetCode 109. 有序链表转换二叉搜索树

约 5 分钟
文章信息 12 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 阿里 微软 拼多多 小红书 快手 猿辅导
标签
树 二叉树 链表 二叉搜索树 分治

题目描述

✅ 109. 有序链表转换二叉搜索树

image-20260928220441695

image-20260928220441697

题意分析

给定一条按升序排列的单链表，使用其中全部节点值构造一棵高度平衡的二叉搜索树，返回树的根节点。高度平衡要求每个节点的左右子树高度差都不超过一，不只是整棵树的根满足这个条件。

合法结果可能不唯一，关键是同时满足有序性和平衡性。链表只能沿后继顺序访问，不能像数组一样直接读取中间位置；因此需要解决如何均分树的结构，又不反复扫描链表寻找中点。

解法：按中序顺序构造平衡 BST

核心思路

[!blue]

有序链表从头到尾的值，正好可以作为目标二叉搜索树的中序序列。可以先根据节点数量安排一棵平衡树的形状，再按照“左子树、根、右子树”的顺序依次填入链表值，就不需要在链表中随机取中点。

先遍历一次得到长度 n。递归函数 build(left, right) 中的闭区间表示这一棵子树要占用哪些中序位置，区间本身不访问链表。选择中点 mid 作为根的位置，左侧分配给左子树，右侧分配给右子树。两侧节点数最多相差一，并继续以相同方式均分，因此构造出的各层都能保持高度平衡。

用共享游标 current 指向下一个尚未取值的链表节点。进入某个递归区间时，它指向这个区间的第一个值。先递归构造 [left, mid - 1]，左子树正好取走前面的全部值；返回后，游标自然来到中点对应的值，此时才能创建根节点，并将游标推进一次。

接着构造 [mid + 1, right]，消耗右侧剩余值，挂到根的右边。函数返回时，恰好取完当前区间的所有节点，游标停在下一个区间的起点。父调用可以继续使用它，不需要从头查找或把链表复制到数组。

当 left > right 时，区间为空，直接返回空树且不消耗链表节点。对于空链表，初始区间就是 [0, -1]，会自然得到空树。构造过程中只读取链表值和后继，原链表连接保持不变。

解题步骤

  1. 将 current 指向链表头，遍历统计节点数 n。
  2. 调用 build(0, n - 1)；递归中若 left > right，返回空节点。
  3. 计算中点 mid，先构造左侧区间，保存得到的左子树。
  4. 用此时 current 的值创建根节点，并令 current = current.next。
  5. 连接已建好的左子树，再递归构造并连接右侧区间，返回当前根。

代码实现

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)$，不计返回的树。递归每次均分区间，栈深为对数量级；新建的结果树另占 $O(n)$。

关键点总结

[!green]

  • 区间中点只决定根的位置和左右规模，实际节点值始终从链表游标顺序取得。
  • 先建左子树再取根值，才能让链表的升序顺序与树的中序顺序一一对应。
  • 每个递归调用恰好消费自己的区间长度，返回时为父调用保留正确的下一个取值位置。

易错点总结

[!yellow]

  • 在构造左子树之前取根值，会把当前区间最小的值放到根上，破坏中序顺序。
  • 用取值游标统计长度后不重置，会在建树开始时已经走到空节点；当前代码使用另一个指针计数。
  • 把游标作为普通指针参数传递，却不把递归后的新位置返回或共享，父调用无法看到子调用的推进。
  • 空区间条件写成 left >= right 会丢掉单节点子树，正确条件是严格大于。
  • 初始闭区间右端应为 n - 1；多分配一个位置，会在链表耗尽后继续取值。

相似题目

题目 难度 关联与区别
108. 将有序数组转换为二叉搜索树 简单 有序数组可直接定位中点，本题链表可先计长度，再按中序顺序消耗节点建树。
1382. 将二叉搜索树变平衡 中等 同样根据有序中序序列构造平衡BST，输入来源与取数方式不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/14733410
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！