java - 两个二叉搜索树的并集

This question already has answers here:

How to merge two BST's efficiently?
（6个答案）
我需要一些帮助来找出如何合并两个二进制搜索树。我的想法/算法：
1）创建一个新的第三个二叉搜索树，以保持其他两个树的并集。
2）遍历第一棵树，将其所有后续元素复制到新创建的树中。
3）按照上述步骤穿过第二棵树。
我有一个add函数，它负责重复并将内容放入树中，所以这部分不成问题我的问题是我不知道如何遍历每个节点并单独操作它们。我在想穿过这棵树

public void inOrderTraverseTree(Node focusNode) {
        if (focusNode != null) {
             preorderTraverseTree(focusNode.leftChild);
             //this is where I can do an operation on the node
             preorderTraverseTree(focusNode.rightChild);

我想取每个连续的节点并将其添加到我的第三个二叉树中据我所见，用上面的函数的任何变体都是不可能实现的还有别的办法吗？它需要完全不同的算法吗？

最佳答案

两个二进制搜索树b1和b2可以合并，而无需使用任何新的数据结构/内存。
我们可以对1棵树进行后序遍历，比如b1，逐个删除其节点，然后将它们插入到另一棵b2中。
通过这种方法，B2将包含原始B1的所有节点，B2和B1将在同一进程中被释放。