本文详解如何在不额外排序的前提下，将两棵bst的所有节点值合并为一个升序列表，重点介绍基于双栈迭代的o(m+n)时间复杂度解法，并对比分析递归同步遍历的不可行性。
本文详解如何在不额外排序的前提下，将两棵bst的所有节点值合并为一个升序列表，重点介绍基于双栈迭代的o(m+n)时间复杂度解法，并对比分析递归同步遍历的不可行性。
二叉搜索树（BST）的核心性质是：中序遍历结果天然有序。因此，合并两个BST的升序结果，本质上等价于合并两个已排序序列——这正是归并排序中“归并”步骤的经典问题。但关键挑战在于：我们无法预先获取完整中序序列（否则需O(m+n)空间存储），也不能用简单递归同时驱动两棵树的深度优先遍历。
❌ 为什么不能用纯递归同步遍历？
直觉上，可能设想定义一个递归函数 recurse(TreeNode r1, TreeNode r2, List<Integer> res)，根据 r1.val 和 r2.val 的大小关系决定向哪棵树深入。但这是不可行的：
- 递归调用栈是单线程的，一次 return 只能回退一棵树的状态，无法独立维护两棵树各自的“当前最左未访问节点”；
- BST 中序依赖隐式栈（调用栈或显式栈）来记住回溯路径，而双树递归会混淆两者的上下文，导致指针丢失或重复访问；
- 不存在一种递归结构能保证“每次只推进较小值对应树的中序进度”，而不破坏另一棵树的状态一致性。
因此，任何试图用单一递归函数同步控制两棵BST遍历的方案，都会在边界情况（如某棵树提前遍历完、空子树、值相等等）下逻辑崩溃或难以维护状态。
✅ 正确解法：双栈模拟双指针中序迭代
最优解是用两个显式栈分别模拟两棵BST的中序迭代器，结合类似归并的逻辑逐个提取最小值：
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack1 = new ArrayDeque<>();
Deque<TreeNode> stack2 = new ArrayDeque<>();
TreeNode node1 = root1, node2 = root2;
while (node1 != null || !stack1.isEmpty() || node2 != null || !stack2.isEmpty()) {
// 向左到底，压入所有左链节点（模拟中序的“找最左”）
while (node1 != null) {
stack1.push(node1);
node1 = node1.left;
}
while (node2 != null) {
stack2.push(node2);
node2 = node2.left;
}
// 比较栈顶（即当前可得的最小候选值），取较小者
if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
TreeNode curr = stack1.pop();
result.add(curr.val);
node1 = curr.right; // 推进到右子树，继续中序
} else {
TreeNode curr = stack2.pop();
result.add(curr.val);
node2 = curr.right;
}
}
return result;
}✅ 时间与空间复杂度
- 时间复杂度：O(m + n) —— 每个节点最多入栈、出栈各一次；
- 空间复杂度：O(h₁ + h₂) —— 栈深取决于两棵树的最大高度，远优于全量存储中序序列的 O(m + n) 空间（方法1）。
⚠️ 关键注意事项
- 判空逻辑必须严谨：stack2.isEmpty() 优先判断，避免对空栈调用 peek()；
- <= 而非 < 保证相等值时优先取 root1 的元素，符合稳定归并语义；
- node1/node2 在每次循环开始时被重置为 null，确保新左链扫描从头开始；
- 该解法天然支持任意数量BST扩展（只需增加栈和节点变量）。
? 对比其他方法
| 方法 | 时间复杂度 | 空间复杂度 | 是否推荐 | 说明 |
|---|---|---|---|---|
| 两遍中序 + 排序 | O((m+n) log(m+n)) | O(m+n) | ❌ | 浪费BST有序性，排序冗余 |
| 自定义双迭代器类（如原题MyIterator） | O(m+n) | O(h₁+h₂) | ✅ | 封装性好，但代码量大 |
| 双栈归并（本文推荐） | O(m+n) | O(h₁+h₂) | ✅✅✅ | 简洁、高效、无额外类、易理解 |
综上，面对“合并多棵BST有序序列”的需求，应放弃同步递归幻想，坚定采用双栈迭代+归并逻辑这一经典范式——它既尊重BST的数学本质，又具备工程落地所需的简洁性与鲁棒性。
