如何合并两棵二叉搜索树中的所有元素并按升序输出？

简化版

分别中序遍历两棵 BST 得到两个有序数组，再像归并排序一样合并即可。时间 O(m+n)，空间 O(m+n)。若要降低额外空间，可以用两个中序迭代器边遍历边归并。

详细版

BST 中序遍历是升序。合并两棵 BST 的所有元素，本质是合并两个有序序列：

对 root1 中序遍历得到 a；
对 root2 中序遍历得到 b；
用两个指针 i,j 归并；
每次把较小元素加入答案；
某一数组用完后，把另一数组剩余部分追加。

该方法清晰稳定，时间 O(m+n)，空间 O(m+n)。进阶做法用两个显式栈模拟中序迭代器，不提前保存完整数组，输出之外额外空间 O(h1+h2)。

完整版教学

一、题目本质是什么

题目说的是两棵 BST，但目标是「所有元素升序输出」。BST 给我们的最大帮助仍然是中序有序，所以它本质上是两个有序序列的归并问题。先把两棵树分别摊平成有序数组，再归并，思路和归并排序的 merge 阶段完全一样。

例如第一棵中序是 [1,4,8]，第二棵中序是 [0,2,7,9]，合并结果就是 [0,1,2,4,7,8,9]。没有必要把节点全部丢进一个数组再排序，因为中序已经帮我们完成了局部排序。

记忆钩子：两棵 BST 合并，不是树上硬拼，而是「两条有序流水线」做归并。

二、为什么不能直接按根节点比较

很多同学会想比较两个根，谁小就先输出谁。这是错误的，因为 BST 的最小值不一定在根，而是在最左侧节点。根只是在自己的左右子树之间起分割作用，并不代表全树当前最小值。

例如一棵树根是 10，但左子树有 1；另一棵树根是 3。直接比较根会先输出 3，可真实最小值是 1。必须通过中序遍历或中序迭代器拿到每棵树的当前最小未输出值。

三、数组版代码最稳

数组版分两步：中序收集、双指针归并。虽然空间不是最优，但正确性最容易讲清楚，面试写起来也最少踩坑。

List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
    List<Integer> a = new ArrayList<>();
    List<Integer> b = new ArrayList<>();
    inorder(root1, a);
    inorder(root2, b);

    List<Integer> ans = new ArrayList<>();
    int i = 0, j = 0;
    while (i < a.size() || j < b.size()) {
        if (j == b.size() || (i < a.size() && a.get(i) <= b.get(j))) {
            ans.add(a.get(i++));
        } else {
            ans.add(b.get(j++));
        }
    }
    return ans;
}

<= 可以保证相等值都被保留。题目要求输出所有元素，所以重复值不能去重。

四、归并过程的数字推演

用两个数组推一遍：

a 当前	b 当前	输出	指针变化
1	0	0	`j++`
1	2	1	`i++`
4	2	2	`j++`
4	7	4	`i++`
8	7	7	`j++`
8	9	8	`i++`

归并的循环不变量是：答案里始终保存已经见过的最小若干元素，两个指针分别指向各自数组中还没输出的最小元素。

五、双栈迭代器如何优化空间

如果不想保存两个完整数组，可以为每棵树维护一个中序迭代器。迭代器内部有一个栈，初始化时压入从根到最左节点的路径；每次取出栈顶节点后，再把它右子树的左链压入栈。这样每次都能得到当前最小未输出值。

Iterator1 -> 当前 root1 的最小未输出值
Iterator2 -> 当前 root2 的最小未输出值
比较两个 peek，输出较小者并推进对应迭代器

空间从 O(m+n) 降到 O(h1+h2)，但实现要支持 peek 和 next，代码复杂度更高。面试中可以先给数组版，再说明优化方向。

六、复杂度和边界

数组版访问每个节点一次，归并又访问每个元素一次，总时间 O(m+n)。空间包括两个中序数组和答案，若答案不计，额外空间 O(m+n)；若用迭代器，输出之外额外空间 O(h1+h2)。

情况	处理
一棵树为空	直接返回另一棵树的中序结果
两棵树都为空	返回空列表
有重复值	全部保留，不去重
树退化	递归栈或迭代栈可能到 O(n)

边界里最容易错的是重复值。题目说所有元素，不是集合，所以相同值出现几次就输出几次。

七、常见误区与追问

误区：合并两棵 BST 要先把它们结构合成一棵树。 题目只要求升序元素列表，不需要改变树结构。
追问：为什么不能比较两个根谁小？ 根不一定是当前最小，最小值在中序遍历的最左侧。
误区：合并后要去重。 输出所有元素，重复节点值要按出现次数保留。
追问：如何把空间优化到 O(h1+h2)？ 用两个中序迭代器，边取当前最小值边归并。
误区：收集完两个数组后还要整体排序。 两个数组已经分别有序，只需线性归并。

八、加强记忆

这题不要想着「树和树怎么合并」，要想着「BST 中序生成有序流」。两棵树就是两条有序流，之后按归并排序的 merge 逻辑输出即可。数组版最稳：先中序，再双指针；优化版更省空间：两个中序迭代器，谁小弹谁。重复值保留、空树直接接上另一边，这几个边界说清楚就很完整。

简化版

详细版