如何用递归实现两棵二叉搜索树的升序元素合并？

给定两棵二叉搜索树（BST），要求返回一个包含所有元素且按升序排列的Java Integer类型List。

已有解法回顾 #

• 解法1：分别对两棵BST执行中序遍历，将遍历结果合并到同一个List后调用排序方法。这种方式实现简单，但时间复杂度为O((m+n)log(m+n))，主要开销来自最后的排序步骤。
• 解法2：实现BST迭代器，通过两个迭代器模拟归并排序的合并过程，时间复杂度为O(m+n)。以下是该方案的实现代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class MyIterator {
    TreeNode root;
    Stack<TreeNode> s;

    public void pushToStack(TreeNode node) {
        while(node!=null) {
            s.push(node);
            node = node.left;
        }
    }

    public boolean hasNext() {
        return s.size()>0;
    }

    public int peek() {
        return s.peek().val;
    }

    public int getNext() {
        var retVal = s.pop();
        if(retVal.right!=null) {
            pushToStack(retVal.right);
        }
        return retVal.val;
    }

    public MyIterator(TreeNode root) {
        s = new Stack<>();
        this.root = root;
        pushToStack(root);
    }
}

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        var iterator1 = new MyIterator(root1);
        var iterator2 = new MyIterator(root2);

        List<Integer> lst = new ArrayList<>();
        while(iterator1.hasNext() && iterator2.hasNext()) {
            if(iterator1.peek()<iterator2.peek()) {
                lst.add(iterator1.getNext());
            } else {
                lst.add(iterator2.getNext());
            }
        }
        while(iterator1.hasNext()) {
                lst.add(iterator1.getNext());
        }
        while(iterator2.hasNext()) {
                lst.add(iterator2.getNext());
        }
        return lst;
    }
}

递归双树实现方案 #

要实现同时递归两棵树的recurse(TreeNode root1, TreeNode root2, List<Integer> lst)方法，核心思路是模拟归并过程的递归版本：遵循BST中序遍历的左->根->右顺序，先处理完两棵树的左子树，再比较当前根节点的值，优先加入较小的元素，然后递归处理对应节点的右子树，直到其中一棵树处理完毕，再把另一棵树剩余的中序元素全部加入列表。

完整代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> result = new ArrayList<>();
        recurse(root1, root2, result);
        return result;
    }

    private void recurse(TreeNode root1, TreeNode root2, List<Integer> lst) {
        // 先递归处理两棵树的左子树，确保左子树的元素都已加入列表
        if (root1 != null && root2 != null) {
            recurse(root1.left, root2.left, lst);
        } else if (root1 != null) {
            // 如果root2为空，对root1执行完整中序遍历
            recurse(root1.left, null, lst);
            lst.add(root1.val);
            recurse(root1.right, null, lst);
            return;
        } else if (root2 != null) {
            // 如果root1为空，对root2执行完整中序遍历
            recurse(null, root2.left, lst);
            lst.add(root2.val);
            recurse(null, root2.right, lst);
            return;
        } else {
            // 两棵树都为空，直接返回
            return;
        }

        // 两棵树左子树处理完毕，比较当前根节点值
        if (root1.val < root2.val) {
            lst.add(root1.val);
            // 递归处理root1的右子树和root2的当前节点
            recurse(root1.right, root2, lst);
        } else {
            lst.add(root2.val);
            // 递归处理root2的右子树和root1的当前节点
            recurse(root1, root2.right, lst);
        }
    }
}

代码逻辑说明

1. 左子树优先处理：递归调用先处理两棵树的左子树，保证中序遍历的顺序（左子树元素都小于当前根节点）。
2. 空节点分支处理：如果其中一棵树的当前节点为空，直接对另一棵树执行完整的中序遍历，把剩余元素加入列表。
3. 根节点比较与递归：当两棵树的当前节点都不为空时，比较值大小，将较小的元素加入列表，然后递归处理该节点的右子树和另一棵树的当前节点，继续归并过程。
4. 终止条件：当两棵树的当前节点都为空时，递归结束。

这种方法的时间复杂度为O(m+n)，和迭代器归并方案一致，空间复杂度主要来自递归栈，最坏情况下为O(m+n)（树退化为链表时）。

内容的提问来源于stack exchange，提问作者curiousengineer