合并两棵二叉树

在以下教程中，我们将了解如何将两棵二叉树合并为一棵二叉树。

难度级别： 简单

面试公司： Adobe、Amazon、Microsoft、Hike

重要成果： 这是一个通过迭代和递归前序遍历理解问题解决的绝佳问题。

理解问题

有两棵二叉树，根节点分别为 first_root 和 second_root，我们需要编写一个程序将这些树合并为一棵二叉树。

为了解决这个问题，想象将一棵树放在另一棵树上进行覆盖。我们会注意到两棵树的一些节点重叠，而另一些则不重叠。

合并规则规定，如果两个节点重叠，则将节点值相加作为合并节点的新值。否则，非空节点将用作合并节点的新值。

我们需要返回合并后树的根节点。

合并过程必须从两棵树的根节点开始。

示例 1

输入

输出

     Merged Tree
          8
         / \
        7   5
       / \   \
      7   2   8

示例 2

输入

输出

     Merged Tree
          7
         / \
        6   8
       / \   \
      5   1   6

理解解决方案方法

以下是我们用于解决问题的一些方法

1. 第一种解决方案方法：使用前序遍历
2. 第二种解决方案方法：使用栈
3. 第三种解决方案方法：使用 BFS 遍历

让我们详细了解上述每种方法。

第一种解决方案方法：使用前序遍历

这种解决方案方法的主要思想是借助前序遍历访问输入二叉树的每个节点，并验证它们在两棵树中的存在。如果两棵树中的选定节点都不是 NULL，我们将把它们的值相加并更新第一棵树中当前节点的值。遍历结束时，第一棵树将是输出，即 合并后的二叉树。

解决问题的步骤

以下是我们将使用前序遍历方法解决此问题的一些步骤

步骤 1： 首先，我们将以前序方式遍历两棵树。

步骤 2： 然后，我们将检查是否有任何一棵树是 NULL，并返回另一棵树的根作为输出。否则，我们将重叠节点的 first_root 和 second_root 相加，并用结果值更新 first_root 的值。

步骤 3： 之后，我们将通过调用相同的函数递归合并两棵树的左子树，并将其分配给 first_root 的左节点。

步骤 4： 然后，我们将通过调用相同的函数递归合并两棵树的右子树，并将其分配给 first_root 的右节点。

步骤 5： 最后，我们将返回合并后树的根节点，即 first_root。

现在让我们看看这个解决方案的伪代码。

解决方案的伪代码

现在让我们考虑以下说明相同的伪代码。

伪代码

时间和空间复杂度分析

假设两棵树中的节点数量分别为 x 和 y。

因此，在最坏的情况下，我们将递归访问 min(x, y) 个节点，对每个节点执行 O(1) 操作。因此，这种方法的时间复杂度将是 O(min(x, y))。

此外，在最坏的情况下，对于倾斜树，递归树的深度可以达到 min(x, y)。因此，空间复杂度将是 O(min(x, y))。

第二种解决方案方法：使用栈进行迭代前序遍历

现在我们将尝试通过迭代前序遍历两棵树来解决给定问题。主要目标是合并两棵树，以便我们能够借助栈同时跟踪两棵树的节点。为了实现这个目标，我们将在栈中以节点对的形式存储数据：{firstTreeNode, secondTreeNode}。这里，firstTreeNode 和 secondTreeNode 分别是第一棵树和第二棵树的节点。

解决问题的步骤

以下是我们将使用栈通过迭代前序遍历解决此问题的一些步骤

步骤 1： 我们将首先创建一个栈来存储两棵树的节点对。

步骤 2： 我们将两棵树的根节点推入栈中。

步骤 3： 我们将运行一个循环，直到栈为空。对于每次迭代，我们将遵循以下一组规则

步骤 3.1： 我们将从栈中移除一个节点对，并用它们的值之和更新第一棵树中对应的节点。

步骤 3.2： 如果当前两个节点都是 NULL，我们将继续从栈中弹出下一对节点。

步骤 3.3： 如果第一棵树的左子节点不是 NULL，我们将两棵树的左子节点推入栈中。

步骤 3.4： 如果第一棵树的左子节点是 NULL，我们将第二棵树的左子节点追加到第一棵树的当前节点。

步骤 3.5： 我们将对右子节点对继续相同的过程。

步骤 4： 最后，我们将返回合并后树的根节点，即 first_root。

现在让我们看看这个解决方案的伪代码。

解决方案的伪代码

现在让我们考虑以下说明相同的伪代码。

伪代码

时间和空间复杂度分析

假设两棵树中的节点数量分别为 x 和 y。

因此，在最坏的情况下，我们将递归访问 min(x, y) 个节点，对每个节点执行 O(1) 操作。因此，这种方法的时间复杂度将是 O(min(x, y))。

此外，在最坏的情况下，对于倾斜树，栈空间的大小将是 min(x, y)。因此，空间复杂度将是 O(min(x, y))。

第三种解决方案方法：使用 BFS 或层序遍历

这种解决方案方法的主要思想是通过按相同顺序访问树的每个节点并添加其相应节点的值来合并两棵树。因此，我们也可以借助广度优先搜索 (BFS) 或层序遍历来解决此问题，其中我们将以逐层方式合并两棵树。

实现的思想与上述方法类似；但是，我们将使用队列数据结构来跟踪节点的顺序并合并它们的值。

现在让我们看看这个解决方案的伪代码。

解决方案的伪代码

现在让我们考虑以下说明相同的伪代码。

伪代码

时间和空间复杂度分析

假设两棵树中的节点数量分别为 x 和 y。

因此，在最坏的情况下，我们将递归访问 min(x, y) 个节点，对每个节点执行 O(1) 操作。因此，这种方法的时间复杂度将是 O(min(x, y))。

注意
建议将上述伪代码转换为 C、C++、Java、Python 等有利的编程语言，并验证所有测试。

用 C 语言将两棵二叉树合并为一棵二叉树的完整程序

现在让我们看看上面所示的伪代码之一在 C 编程语言中的完整转换。

代码

输出

The New Merged Binary Tree is : 
7 7 2 8 8 5

说明

在上面的代码片段中，我们分别包含了必要的头文件，如 stdio.h 和 stdlib.h。然后，我们使用 struct 语句定义了一个结构，其中定义了存储整数数据类型的数据成员以及指向左子节点和右子节点的两个指针。然后，我们定义了一个辅助函数，该函数使用给定数据和 NULL 左、右指针分配一个新节点。我们还定义了一个函数，用于以中序方式打印树数据结构的节点。然后，我们定义了一个函数，用于根据递归概念使用前序遍历将两棵二叉树合并为一棵二叉树。在此函数中，我们检查了是否有任何一棵树为空，并返回了另一棵树。如果两棵树都包含一些节点，我们 then 将它们的数据相加，递归地作用于两棵树的左子节点和右子节点，将结果值分别存储在第一棵树的节点中，并将其作为结果返回。然后，我们定义了 main 函数，其中我们声明了两棵树的每个节点的值。然后，我们调用了 mergeBinTree() 函数来执行合并过程并将结果存储在另一棵树中。最后，我们调用了 inorder() 函数来打印结果树的节点值。

结论

在上述教程中，我们学习了将两棵二叉树合并为一棵二叉树的不同方法。