汀的知识碎片

08 有序序列转平衡搜索树：数组与链表两种输入

5 min read

有序序列转平衡搜索树：数组与链表两种输入

摘要

LeetCode 108 和 109 都要求把有序序列转成高度平衡的 二叉搜索树。这两道题表面上几乎一样，一个输入数组，一个输入链表，实际上因为底层存储结构不同，解法细节差异很大。数组支持随机访问，因此可以天然用中点做根；链表不支持随机访问，所以不能直接照抄数组解法。本文会从“为什么取中点会平衡”这个问题出发，比较数组版和链表版的两种主流实现。

第 1 章 LeetCode 108：有序数组转 BST

1.1 为什么中点做根能保证平衡

数组是有序的，如果取中点作为根：

  • 左边所有元素都小于根，可构成左子树
  • 右边所有元素都大于根，可构成右子树
  • 左右两边元素数量尽量接近，因此树高度尽量平衡

这其实是“有序 + 平衡”两个目标的最自然统一。

1.2 代码实现

public TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
 
private TreeNode build(int[] nums, int left, int right) {
    if (left > right) {
        return null;
    }
 
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, left, mid - 1);
    root.right = build(nums, mid + 1, right);
    return root;
}

这是一道标准分治题：根由中点决定，左右区间继续递归。

第 2 章 LeetCode 109：有序链表转 BST

2.1 为什么不能直接按数组思路做

链表没有下标访问，拿中点必须线性扫描。如果每层递归都从头找中点，虽然能做出来，但效率和代码结构都比数组版差。

2.2 方案一：快慢指针找中点

public TreeNode sortedListToBST(ListNode head) {
    return build(head, null);
}
 
private TreeNode build(ListNode head, ListNode tail) {
    if (head == tail) {
        return null;
    }
 
    ListNode slow = head;
    ListNode fast = head;
    while (fast != tail && fast.next != tail) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    TreeNode root = new TreeNode(slow.val);
    root.left = build(head, slow);
    root.right = build(slow.next, tail);
    return root;
}

这个写法和数组版思想一致，只是“找中点”从 O(1) 变成了 O(n)。整体复杂度是 。

2.3 方案二：模拟中序构造

更优雅的做法是：

  1. 先遍历链表求长度 n
  2. 按中序构造 BST
  3. 左子树建完后，当前链表节点正好对应根
  4. 再继续建右子树
private ListNode current;
 
public TreeNode sortedListToBST(ListNode head) {
    int length = 0;
    current = head;
    while (head != null) {
        length++;
        head = head.next;
    }
    return buildTree(0, length - 1);
}
 
private TreeNode buildTree(int left, int right) {
    if (left > right) {
        return null;
    }
 
    int mid = left + (right - left) / 2;
    TreeNode leftChild = buildTree(left, mid - 1);
 
    TreeNode root = new TreeNode(current.val);
    current = current.next;
 
    root.left = leftChild;
    root.right = buildTree(mid + 1, right);
    return root;
}

这个写法把链表线性顺序和 BST 中序顺序完美对应起来，复杂度可降到 。

第 3 章 两道题真正考的是什么

题目输入结构关键操作复杂度
LC108数组O(1) 取中点O(n)
LC109链表找中点或模拟中序O(n log n) 或 O(n)

这两道题看似是 BST 题，其实也在考你是否尊重底层数据结构的访问成本。

不要忽视“随机访问能力”

同样是有序序列，数组和链表的算法设计差异往往不在逻辑，而在访问成本。把数组思路原样搬到链表上，经常就会把复杂度做坏。

下一篇预告

09 二叉树深度问题：最小深度、最大深度与 BFS-DFS 取舍 会从构造专题回到遍历与返回值专题。最小深度和最大深度经常被放在一起问，但判断逻辑并不对称，这恰好是树题里非常经典的陷阱。

Backlinks