合并两个平衡二叉搜索树

在此问题中，我们给定两个平衡二叉搜索树。我们需要创建一个函数来将这两个二叉搜索树合并成一个单一的搜索树。假设其中一棵二叉树有 m 个元素，而第二棵二叉树有 n 个节点。我们需要创建一个高效的函数，能够以最佳时间合并这两棵二叉树。

方法 - 1

此方法将从给定的两棵树创建一个新的合并树。我们将按照以下步骤创建此树。

• 首先，我们将定义一个函数，该函数给出树的中序遍历。通过这种方式，我们将获得两个二叉搜索树的中序遍历。正如我们所知，二叉搜索树的中序遍历是排序的。
• 然后，我们将创建一个函数来合并两个排序数组。这些数组是给定二叉搜索树的中序遍历。我们将通过线性循环遍历这两个数组来合并这两个数组。我们将合并后的数组存储在一个新数组中。
• 现在我们有了一个合并后的排序数组，它将作为我们必须创建的新二叉搜索树的中序遍历。因此，我们将定义一个函数，该函数将中序遍历转换为树。
• 这将是我们的最终合并二叉搜索树。

以下是此方法的 Python 代码。

代码

输出

The first binary search tree is: [2, 5, 7, 10, 30]
The second binary search tree is: [4, 8, 12]
The Inorder traversal of the merged binary search tree
2 4 5 7 8 10 12 30

时间复杂度：此程序的 time complexity 为 O(m+n)，其中 m 和 n 是两棵二叉搜索树的节点数。我们使用了线性循环来遍历两棵二叉树以存储中序遍历并合并两个数组。

空间复杂度：此程序的 space complexity 将是用于存储数组中序遍历的数组所占用的总空间。第一棵二叉搜索树将占用 O(m) 空间，第二棵将占用 O(n) 空间。因此，总空间复杂度为 O(m+n)。

方法 - 2

此方法将使用双向链表来创建合并的二叉搜索树。此方法比前一种方法更好，因为树将在原地创建。以下是使用此方法解决问题的步骤

• 我们可以使用双向链表来原地合并树。以下是步骤。
• 我们将把给定的两棵二叉树转换为双向链表数据结构。
• 然后，我们将合并这两个双向链表。
• 在最后一步，我们将合并后的双向链表转换为二叉搜索树。这将是我们需要的合并二叉搜索树。

代码

输出

The inorder traversal of the merged binary search tree is:
2 4 5 7 8 10 12 30

时间复杂度：此程序的 time complexity 是线性的。我们只使用了线性循环来执行所有必需的操作。因此，time complexity 为 O(m + n)，其中 m 和 n 是两棵二叉搜索树的节点数。

辅助空间：我们没有使用额外的空间来存储二叉树和链表。因此，此方法的 space complexity 是常数，即 O(1)。