本文详解如何在不额外排序的前提下，将两棵bst的所有节点值合并为一个升序列表，重点介绍基于双栈迭代的o(m+n)时间复杂度解法，并对比分析递归同步遍历的不可行性。
本文详解如何在不额外排序的前提下，将两棵bst的所有节点值合并为一个升序列表，重点介绍基于双栈迭代的o(m+n)时间复杂度解法，并对比分析递归同步遍历的不可行性。
二叉搜索树（BST）的核心性质是：中序遍历结果天然有序。因此，将两棵BST的所有元素按升序合并，本质是将两个已排序序列进行归并（merge）。关键在于——我们不能真正执行两次完整中序遍历再合并（那样虽可行但需O(m+n)空间存中间结果，且排序步骤冗余），而应模拟“懒加载式”的双指针遍历，每次只推进当前较小元素所在树的遍历进度。
为什么无法用纯递归同步遍历？
直觉上，人们常希望设计形如 recurse(TreeNode r1, TreeNode r2, List<Integer> res) 的递归函数，通过比较 r1.val 和 r2.val 决定下一步递归方向。但这是不可行的：
- 递归调用栈是单线程的，一次 recurse() 调用只能进入一棵树的子树，无法独立控制两棵树各自的遍历深度；
- BST 中序依赖隐式栈（系统栈或手动栈）维护“回溯路径”，而两棵树的回溯路径完全独立——强行耦合会导致逻辑错乱，例如当 r1 需向左深入、r2 需向右回溯时，递归无法同时满足二者状态；
- 所谓“同步递归”本质上混淆了控制流与数据流：归并需要的是两个独立、可暂停/恢复的遍历器（iterator），而非共享同一调用栈的递归分支。
因此，正确思路是：用迭代 + 双栈显式模拟两个独立的中序遍历器，再套用归并逻辑。
双栈迭代归并：清晰、高效、无额外排序
以下实现使用 Deque<TreeNode> 作为栈（比 Stack 更高效且线程安全），核心思想是：
- 双路入栈：分别将两棵树当前最左路径压入各自栈中；
- 择小弹出：比较两栈顶节点值，弹出较小者，加入结果，并将其右子树的最左路径压入对应栈；
- 循环直至双栈均空：注意边界判断需兼顾 node != null 与 stack.isEmpty()。
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)) {
node1 = stack1.pop();
result.add(node1.val);
node1 = node1.right; // 推进到右子树，后续会继续压左链
} else {
node2 = stack2.pop();
result.add(node2.val);
node2 = node2.right;
}
}
return result;
}关键细节与注意事项
- 时间复杂度：O(m + n)，每个节点最多入栈、出栈各一次；
- 空间复杂度：O(h₁ + h₂)，即两树最大高度之和（栈深度），优于一次性存储全部中序结果的 O(m + n)；
- 稳定性：当两节点值相等时，优先取 stack1 中元素，保证相同值的相对顺序（若业务需严格稳定，可调整比较逻辑）；
- 空树鲁棒性：代码中 stack.isEmpty() 与 node == null 的联合判断自然处理了任一树为空的情况；
-
替代方案权衡：
- 方法一（两次中序+排序）：代码简单但时间退化为 O((m+n) log(m+n))，且违背BST有序特性；
- 自定义迭代器（如题中 MyIterator）：逻辑清晰，但封装开销略高；双栈方案更轻量、易理解、无额外类定义。
综上，双栈归并是兼顾效率、简洁性与工程实践的最佳选择——它精准利用BST的结构性质，将抽象的“两个有序流归并”落地为可控的迭代操作，是解决此类问题的典范模式。
