1. 概述
二叉搜索树（Binary Search Tree，简称 BST） 是一种非常基础的数据结构，属于二叉树的一种。它的核心特性是：任意节点的左子节点值小于该节点，右子节点值大于该节点。
在本教程中，我们将学习两种合并两个 BST 的算法，并分析它们的时间与空间复杂度（Big O 表示法）。复杂度分析对于评估算法性能非常重要，它能帮助我们了解算法在时间和空间上的开销。
下图展示了两个 BST（BST1 和 BST2）合并后的结果。合并后的 BST 包含了 BST1 和 BST2 中的所有元素，并保持 BST 的特性：
2. 合并、排序、重建
该算法的核心思想是：
- 将两个 BST 的元素分别提取到数组中；
- 合并这两个数组并进行排序；
- 使用排序后的数组重建一个新的 BST。
✅ 算法步骤：
- 提取元素：分别对 BST1 和 BST2 进行中序遍历，将元素存储到两个数组中；
- 合并排序：将两个数组合并成一个，并使用排序算法（如快速排序、归并排序等）进行排序；
- 重建 BST：使用排序后的数组构建一个新的平衡 BST。
⏱️ 时间复杂度分析：
- 提取元素：
O(n1 + n2)，其中n1和n2是两个 BST 的节点数。 - 排序：
O(n log n)，如果使用归并排序或快速排序。 - 重建 BST：
O(n)，其中n = n1 + n2。
📦 空间复杂度：
O(n)，因为需要额外的数组来存储所有节点。
✅ Java 示例代码：
public class MergeBSTBySorting {
public static TreeNode mergeBSTs(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
// Step 1: 中序遍历提取元素
inOrderTraversal(root1, list1);
inOrderTraversal(root2, list2);
// Step 2: 合并并排序
List<Integer> merged = new ArrayList<>();
merged.addAll(list1);
merged.addAll(list2);
Collections.sort(merged);
// Step 3: 构建新 BST
return buildBST(merged, 0, merged.size() - 1);
}
private static void inOrderTraversal(TreeNode root, List<Integer> list) {
if (root == null) return;
inOrderTraversal(root.left, list);
list.add(root.val);
inOrderTraversal(root.right, list);
}
private static TreeNode buildBST(List<Integer> list, int start, int end) {
if (start > end) return null;
int mid = (start + end) / 2;
TreeNode node = new TreeNode(list.get(mid));
node.left = buildBST(list, start, mid - 1);
node.right = buildBST(list, mid + 1, end);
return node;
}
}
⚠️ 踩坑提醒：
- 如果使用冒泡排序等低效排序算法，复杂度会退化到
O(n²)，不推荐。 - 此方法适用于节点数量不大或需要构建平衡 BST 的场景。
3. 遍历、归并、重建
该算法的核心思想是利用两个 BST 的中序遍历结果是有序数组的特性，像归并排序一样合并两个有序数组，然后重建 BST。
✅ 算法步骤：
- 对两个 BST 分别进行中序遍历，得到两个有序数组；
- 归并这两个有序数组为一个有序数组；
- 使用该有序数组构建一个新的 BST。
⏱️ 时间复杂度分析：
- 中序遍历：
O(n1 + n2) - 归并排序：
O(n1 + n2) - 重建 BST：
O(n) - 总体时间复杂度：
O(n1 + n2)
📦 空间复杂度：
O(n1 + n2)，需要两个数组存储遍历结果。
✅ Java 示例代码：
public class MergeBSTByMergingInOrder {
public static TreeNode mergeBSTs(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
// Step 1: 中序遍历提取元素
inOrderTraversal(root1, list1);
inOrderTraversal(root2, list2);
// Step 2: 归并两个有序数组
List<Integer> merged = new ArrayList<>();
int i = 0, j = 0;
while (i < list1.size() && j < list2.size()) {
if (list1.get(i) < list2.get(j)) {
merged.add(list1.get(i++));
} else {
merged.add(list2.get(j++));
}
}
while (i < list1.size()) merged.add(list1.get(i++));
while (j < list2.size()) merged.add(list2.get(j++));
// Step 3: 构建新 BST
return buildBST(merged, 0, merged.size() - 1);
}
private static void inOrderTraversal(TreeNode root, List<Integer> list) {
if (root == null) return;
inOrderTraversal(root.left, list);
list.add(root.val);
inOrderTraversal(root.right, list);
}
private static TreeNode buildBST(List<Integer> list, int start, int end) {
if (start > end) return null;
int mid = (start + end) / 2;
TreeNode node = new TreeNode(list.get(mid));
node.left = buildBST(list, start, mid - 1);
node.right = buildBST(list, mid + 1, end);
return node;
}
}
⚠️ 踩坑提醒：
- 这个方法比“先合并后排序”更高效，因为利用了 BST 的中序遍历是有序数组这一特性；
- 如果你希望合并后的 BST 也是平衡的，可以考虑此方法；
- 不建议手动实现归并逻辑时写错边界条件，容易越界。
4. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 合并、排序、重建 | O(n log n) |
O(n) |
实现简单，适合节点不多的场景 |
| 遍历、归并、重建 | O(n) |
O(n) |
更高效，推荐使用，适合大规模数据 |
✅ 总结建议：
- 若对性能要求较高，推荐使用“遍历、归并、重建”方案；
- 若节点数量不多，且对平衡性无要求，可以使用“合并、排序、重建”；
- 合并 BST 的关键在于利用中序遍历的有序性，这是 BST 的核心特性之一。