1. 概述
在本篇文章中，我们将讨论如何从一个有序列表中构建一个平衡二叉搜索树（Balanced Binary Search Tree, BST）。我们会介绍两种常见方法：自顶向下（Top-Down） 和 自底向上（Bottom-Up） 方法，并对它们进行比较。
2. 什么是平衡二叉搜索树
一个平衡二叉树是指其高度为 O(log n) 的二叉树，其中 n 是树中节点的总数。对于树中的每个节点，其左右子树的高度差不能超过 1。
而二叉搜索树的定义是：对于每个节点，其左子树的所有节点值都小于该节点值，右子树的所有节点值都大于该节点值。
下面是一个平衡二叉搜索树的示例：
如图所示，节点 4 的左子树包含 2 和 3，都小于 4；右子树包含 5, 6, 7, 8, 9，都大于 4。这种结构在整棵树中保持，使得它既是 BST，又是平衡的。
3. 构建平衡 BST 的思路
要构建一个平衡 BST，核心思想是：
✅ 将中间值作为根节点，左边的值构建左子树，右边的值构建右子树
这样可以保证树的高度尽可能小，从而保持平衡。
根据输入数据的结构不同，主要有两种实现方式：
- Top-Down Approach：适用于数组结构，可以随机访问
- Bottom-Up Approach：适用于链表结构，只能顺序访问
4. 自顶向下方法（Top-Down Approach）
适用于有序数组，实现简单直观。
✅ 实现步骤
- 取数组中间元素作为当前节点（根）
- 递归构建左子树（左半部分）
- 递归构建右子树（右半部分）
✅ 示例代码（Java）
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public class BalancedBST {
public static TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private static TreeNode build(int[] nums, int left, int right) {
if (left > right) return null;
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, left, mid - 1);
root.right = build(nums, mid + 1, right);
return root;
}
}
⚠️ 时间复杂度
- **时间复杂度：O(n)**，每个节点仅被访问一次
- **空间复杂度：O(log n)**，递归栈深度
5. 自底向上方法（Bottom-Up Approach）
适用于有序链表，实现稍复杂，但避免了链表随机访问的限制。
✅ 实现思路
- 先递归构建左子树
- 当前节点取链表当前指针指向的节点
- 移动指针到下一个节点
- 递归构建右子树
✅ 示例代码（Java）
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
}
}
public class BalancedBSTFromList {
private static ListNode current;
public static TreeNode sortedListToBST(ListNode head) {
int n = countNodes(head);
current = head;
return build(n);
}
private static int countNodes(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
private static TreeNode build(int n) {
if (n <= 0) return null;
TreeNode left = build(n / 2);
TreeNode root = new TreeNode(current.val);
current = current.next;
TreeNode right = build(n - n / 2 - 1);
root.left = left;
root.right = right;
return root;
}
}
⚠️ 时间复杂度
- **时间复杂度：O(n)**，每个节点仅被访问一次
- **空间复杂度：O(log n)**，递归栈深度
6. 两种方法对比
| 特性 | 自顶向下（Top-Down） | 自底向上（Bottom-Up） |
|---|---|---|
| 数据结构 | 数组 | 链表 |
| 思路 | 先选根节点，再递归构建左右子树 | 先递归到底部构建左子树，再构建当前节点 |
| 实现难度 | 简单 | 稍复杂 |
| 时间复杂度 | O(n) | O(n) |
| 适用场景 | 输入为数组 | 输入为链表 |
✅ Top-Down 更适合数组，实现简单直观
✅ Bottom-Up 更适合链表，避免了链表无法随机访问的问题
7. 总结
本文介绍了两种从有序列表构建平衡 BST 的方法：
- Top-Down Approach：适合数组结构，实现简单
- Bottom-Up Approach：适合链表结构，避免随机访问限制
两种方法都具有线性时间复杂度 O(n)，但在不同数据结构下各有优势。
📌 踩坑提醒：
- 使用 Bottom-Up 时要注意链表指针的移动逻辑，避免重复访问或漏掉节点
- Top-Down 虽然简单，但不能直接用于链表，否则会重复遍历导致效率下降
在实际开发中，应根据输入数据的存储结构选择合适的方法。