本文介绍在不额外排序的前提下，以 o(m+n) 时间复杂度合并两个 bst 的所有节点值并返回升序列表的最优解法，重点讲解双栈迭代模拟中序遍历+归并的思想与实现。
本文介绍在不额外排序的前提下，以 o(m+n) 时间复杂度合并两个 bst 的所有节点值并返回升序列表的最优解法，重点讲解双栈迭代模拟中序遍历+归并的思想与实现。
在处理两个二叉搜索树（BST）时，一个经典需求是：将两棵树的所有节点值合并，并以严格升序排列返回 List
更优解法应充分利用 BST 的有序性，避免显式排序。关键洞察在于：我们不需要预先生成完整中序序列，而只需“按需获取”当前最小未访问节点值——这正是归并两个有序流的核心思想。但由于递归难以同步控制两棵树的遍历进度（递归调用栈无法独立暂停/恢复两棵子树），纯递归方式无法直接实现“双指针式”的协同遍历。原因在于：单次递归调用只能深入一棵树的一个分支，返回时会同时回溯两棵树的调用栈，丧失对各自遍历状态的细粒度控制。
因此，工业级可靠解法采用双栈迭代模拟中序遍历 + 归并逻辑，时间复杂度 O(m+n)，空间复杂度 O(h₁+h₂)（h₁、h₂ 为两树高度）。其核心逻辑如下：
- 维护两个栈 stack1 和 stack2，分别模拟树1和树2的中序遍历过程；
- 使用两个指针 node1 和 node2 指向当前待处理节点；
- 循环中：先将各自左链全部压栈（即找到各自最左下节点）；
- 比较两栈顶元素（若某栈为空则取另一栈），弹出较小者，加入结果，并将其右子树作为新起点继续压栈；
- 直到两栈均空且两指针均为 null。
以下是简洁、健壮的 Java 实现：
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 左链全压入 stack1
while (node1 != null) {
stack1.push(node1);
node1 = node1.left;
}
// 将 node2 左链全压入 stack2
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;
}⚠️ 注意事项：
- 边界安全：每次比较前必须检查栈是否为空，避免 peek() 抛出 NoSuchElementException；
- 稳定性保证：当两栈顶值相等时，优先取 stack1 的元素（
- 空间优化：使用 ArrayDeque 替代 Stack（后者基于过时的 Vector，线程安全但性能差）；
-
不可递归化：试图设计 recurse(TreeNode r1, TreeNode r2, List
res) 方法会陷入逻辑死锁——递归无法“暂停”一棵树等待另一棵树推进，本质是双状态机问题，必须依赖显式栈管理。
总结：该双栈归并法兼具时间最优性与代码可读性，是解决“合并两 BST 有序元素”问题的标准范式。它将中序遍历的“左-根-右”过程解耦为可控的压栈/弹栈操作，再结合归并思想，实现了真正意义上的在线（on-the-fly）、流式（streaming）有序合并。
