本文介绍如何高效合并两棵二叉搜索树（bst）的所有节点值，生成一个升序排列的整数列表；重点讲解基于双栈模拟中序遍历+归并思想的迭代解法，避免额外排序开销，时间复杂度 o(m + n)，空间复杂度 o(h₁ + h₂)。
本文介绍如何高效合并两棵二叉搜索树（bst）的所有节点值，生成一个升序排列的整数列表；重点讲解基于双栈模拟中序遍历+归并思想的迭代解法，避免额外排序开销，时间复杂度 o(m + n)，空间复杂度 o(h₁ + h₂)。
在处理两个 BST 的有序合并问题时，核心洞察在于：BST 的中序遍历天然产生升序序列。若将两棵树分别完整中序遍历后合并再排序（如方法一），虽简单但时间复杂度退化为 O((m+n) log(m+n))；而手写双迭代器（如原题中 MyIterator 类）虽可行，但代码冗长、易出错。更优雅的解法是——用两个显式栈替代递归调用栈，同步模拟两棵树的中序遍历过程，并在线归并。
该解法不依赖递归同时遍历两树（事实上，纯递归无法自然实现“单次调用中独立推进两树指针”），而是通过循环 + 双栈精确控制每棵树当前最左未访问节点，始终选取较小者加入结果，并仅向对应树的右子树深入一步，从而保证整体 O(m + n) 时间与最小栈空间。
以下是简洁、健壮的实现：
import java.util.*;
class Solution {
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()) {
// 将 node1 沿左链压栈至最左节点
while (node1 != null) {
stack1.push(node1);
node1 = node1.left;
}
// 将 node2 沿左链压栈至最左节点
while (node2 != null) {
stack2.push(node2);
node2 = node2.left;
}
// 比较栈顶（即当前可得的最小候选值），选择较小者
if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
TreeNode cur = stack1.pop();
result.add(cur.val);
node1 = cur.right; // 向右子树推进，后续会继续压左链
} else {
TreeNode cur = stack2.pop();
result.add(cur.val);
node2 = cur.right;
}
}
return result;
}
}✅ 关键设计说明：
- 双栈独立维护：stack1 和 stack2 分别模拟两棵树的中序遍历状态，互不干扰；
- 统一循环驱动：主循环条件覆盖所有未处理节点（当前节点非空或栈非空），确保无遗漏；
- 贪心归并逻辑：每次只弹出值更小的栈顶节点，添加后立即转向其右子树——这等价于“中序中访问完左子树和根后，进入右子树”，完全复现中序语义；
- 边界安全：通过 stack2.isEmpty() 和 !stack1.isEmpty() 的组合判断，避免空栈 peek() 异常。
⚠️ 注意事项：
- 此解法不可用纯递归替代——因为递归函数调用栈是单线程的，无法在一次递归入口中“暂停一棵树、推进另一棵树”；强行设计多参数递归（如 recurse(root1, root2, list)）将导致逻辑混乱、状态难以维护，违背中序遍历的本质控制流；
- 若需极致空间优化（如应对极深树），可改用 Morris 遍历变体，但会牺牲代码清晰度与安全性；
- 本方案已是最优实践：时间最优（每个节点访问且仅访问一次），空间最优（仅需两树高度之和的栈空间），且代码简洁、无自定义类、易于理解和测试。
综上，面对“合并两 BST 并升序输出”的需求，推荐采用双栈迭代归并法——它精准融合了 BST 性质、中序遍历机制与归并排序思想，是工程与算法美感兼具的标准解。
