您假设所有二叉搜索树都是平衡的。（例如，Splay 树就不是平衡的）另外，我认为您的复杂性略有偏差。由于 n2 在增加，因此随着您插入值，树会变得更深。也许 (n1 + n2) / 2 是更好的近似值（因为在插入开始时插入是 O(log n2)，而在插入结束时是 O(log(n1 + n2))。

@Evan Teran，例如 a<-c->h union b<-d->f，它们的范围 [a,h] 和 [b,f] 重叠，因此都不能作为叶节点插入到另一个节点中

Naaff 的回答更详细一些：

• 将 BST 展平为排序列表需要 O(N)
  • It's just "in-order" iteration on the whole tree.
  • Doing it for both is O(n1+n2)
• 将两个排序列表合并为一个排序列表的复杂度为 O(n1+n2)。
  • Keep pointers to the heads of both lists
  • Pick the smaller head and advance its pointer
  • This is how the merge of merge-sort works
• 从排序列表创建完美平衡的 BST 时间为 O(N)
  • See code snippet below for algorithm[1]
  • In our case the sorted list is of size n1+n2. so O(n1+n2)
  • The resulting tree would be the conceptual BST of binary searching the list

O(n1+n2) 的三个步骤导致 O(n1+n2)

对于同一数量级的 n1 和 n2，这比 O(n1 * log(n2)) 更好

[1] 从排序列表创建平衡 BST 的算法（Python 中）：

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}

无法改进的证明草图：您需要考虑每个元素。在树 1 中的 2 个相邻值之间，树 2 中可能会有 0、1 或更多值。仅查看 N1+N2 个元素就已经花费了 O(N1+N2) 时间。

@MSalters：根据 OP，您可以就地修改一棵树。您不必查看正在修改的树的所有元素

我很难理解为什么创建平衡 BST 的最后一步是 O(N)。由于这里使用的数据结构是一个列表，那么在递归的每个级别中为 n 个元素找到“中间”的复杂度不是 n/2 吗？所以创建平衡 BST 的总复杂度将是 n/2 log n，对吗？如果排序后的数据在数组中，我可以看到如何在 O(N) 中完成此操作。但这里的情况并非如此。我遗漏了什么？

@KarthikM：我的解释确实不太准确，现在将带有实际代码片段的算法添加到答案中。

• 将树展平为排序列表。
• 合并已排序的列表。
• 从合并列表创建树。

若我没记错的话，那是 O(n1+n2)。

正如其他人在我的帖子后指出的那样，此过程的复杂度为 O(n1+n2)。例如，请参阅 yairchu 对我的答案的详细说明。

乔纳森，

排序后，我们得到一个长度为 n1+n2 的列表。用它构建二叉树需要 log(n1+n2) 时间。这与归并排序相同，只是在每个递归步骤中，我们不会像归并排序算法那样有 O(n1+n2) 项。因此时间复杂度为 log(n1+n2)。

现在整个问题的复杂度为O(n1+n2)。

另外，如果两个列表的大小相当，我会说这种方法很好。如果大小不具可比性，那么最好将小树的每个节点插入大树中。这将花费 O(n1*log(n2)) 时间。例如，如果我们有两棵树，一棵树的大小为 10，另一棵树的大小为 1024。这里 n1+n2 = 1034，而 n1log(n2) = 10*10 = 100。因此，方法必须取决于两棵树的大小。

我的意思是构建一个带有排序列表的树的复杂度为 log(n1+n2)。现在整个问题的复杂度为 O(n1+n2)

即使我们将任何未排序列表合并到 BST 中，O(n1 * log(n2)) 也是平均情况。我们没有利用列表是排序列表或 BST 的事实。

根据我假设一个 BST 有 n1 个元素，另一个有 n2 个元素。现在将一个 BST 转换为 O(n1) 中的排序数组列表 L1。

合并 BST(BST，数组)

if (Array.size == 0) return BSTif(Array.size ==1)将元素插入BST。return BST;

找到数组中左元素 < BST.rootnode 且右元素 >=BST.rootnode 的索引，说 Index.if(BST.rootNode.leftNode ==null ) //即没有左节点{将从 Index 到 0 的整个数组插入到 BST 的左侧，}else{合并 BST(BST.leftNode, Array{0 到 Index})}

if(BST.rootNode.rightNode ==null)//即没有右节点{将数组从 Index 到 Array.size 全部插入到 BST 的右侧 }else{ Merged BST(BST.rightNode, Array{Index to Array.size})}

返回 BST。

由于每次我们对数组和 BST 进行分区来处理子问题，因此该算法所花费的时间将比 O(n1 * log(n2)) 要少。

这个想法是使用迭代中序遍历。我们对两个 BST 使用两个辅助堆栈。由于我们需要以排序形式打印元素，因此每当我们从任何一棵树中获得较小的元素时，我们都会打印它。如果元素较大，则我们将其推回堆栈以进行下一次迭代。

双重迭代中序遍历可以工作，但是关于打印出元素，你还在说什么？你应该最终得到一个 BST。