【4.6】图搜索算法-DFS和BFS解合并二叉树
一、题目
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是
如果两个节点重叠，那么将他们的
值相加作为节点合并后的新值，否则不为 NUL L 的节点将直接作为新二叉树的节点
。
示例 1:
合并后的树如下
注意
:
合并必须从两个树的根节点开始。
二、解题思路
DFS思路：
合并两棵二叉树时，可能会遇到以下三种情况：
1. 两个节点都为空：在这种情况下，不需要进行合并操作。
2. 一个节点为空，另一个节点不为空：合并的结果将是不为空的那个节点。
3. 两个节点都不为空：合并后的节点值将是这两个节点值的和。
我们一起画图看看
BFS思路：
除了
DFS
我们还可以使用
BFS
，就是一层一层的遍历，合并的原理和上面一样
这里描述的是将第二棵树合并到第一棵树上的过程：
- 如果第一棵树的左子节点为空，直接将第二棵树的左子节点赋值给第一棵树的左子节点。
- 如果第一棵树的左子节点不为空，而第二棵树的左子节点为空，直接返回第一棵树的左子节点。
- 如果第一棵树的左子节点和第二棵树的左子节点都不为空，直接将它们的值相加。
右子树和上面原理一样。
三、代码实现
DFS代码：
#include <iostream>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
// 如果两个节点都为空，直接返回空
if (t1 == nullptr && t2 == nullptr)
return nullptr;
// 如果t1节点为空，就返回t2节点
if (t1 == nullptr)
return t2;
// 如果t2节点为空，就返回t1节点
if (t2 == nullptr)
return t1;
// 走到这一步，说明两个节点都不为空，然后需要把这两个节点
// 合并成一个新的节点
TreeNode* newNode = new TreeNode(t1->val + t2->val);
// 当前节点t1和t2合并完之后，还要继续合并t1和t2的子节点
newNode->left = mergeTrees(t1->left, t2->left);
newNode->right = mergeTrees(t1->right, t2->right);
return newNode;
}
// 辅助函数：前序遍历打印二叉树
void preOrderPrint(TreeNode* root) {
if (root == nullptr)
return;
cout << root->val << " ";
preOrderPrint(root->left);
preOrderPrint(root->right);
}
int main() {
// 示例二叉树1
TreeNode* t1 = new TreeNode(1);
t1->left = new TreeNode(3);
t1->right = new TreeNode(2);
t1->left->left = new TreeNode(5);
// 示例二叉树2
TreeNode* t2 = new TreeNode(2);
t2->left = new TreeNode(1);
t2->right = new TreeNode(3);
t2->left->right = new TreeNode(4);
t2->right->right = new TreeNode(7);
// 合并两棵二叉树
TreeNode* mergedTree = mergeTrees(t1, t2);
// 打印合并后的二叉树
cout << "合并后的二叉树前序遍历结果: ";
preOrderPrint(mergedTree);
cout << endl;
return 0;
}BFS代码：
#include <iostream>
#include <queue>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 把第2棵树合并到第1棵树上
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
// 如果t1节点为空，就返回t2节点
if (t1 == nullptr)
return t2;
// 如果t2节点为空，就返回t1节点
if (t2 == nullptr)
return t1;
// 队列中两棵树的节点同时存在
queue<TreeNode*> q;
// 把这两棵树的节点同时入队
q.push(t1);
q.push(t2);
while (!q.empty()) {
// 两棵树的节点同时出队
TreeNode* node1 = q.front();
q.pop();
TreeNode* node2 = q.front();
q.pop();
// 把这两个节点的值相加，然后合并到第1棵树的节点上
node1->val += node2->val;
if (node1->left == nullptr) {
// 如果node1左子节点为空，我们直接让node2的
// 左子结点成为node1的左子结点，
node1->left = node2->left;
} else {
// 执行到这一步，说明node1的左子节点不为空，
// 如果node2的左子节点为空就不需要合并了，
// 只有node2的左子节点不为空的时候才需要合并
if (node2->left != nullptr) {
q.push(node1->left);
q.push(node2->left);
}
}
// 原理同上，上面判断的是左子节点，这里判断的是右子节点
if (node1->right == nullptr) {
node1->right = node2->right;
} else {
if (node2->right != nullptr) {
q.push(node1->right);
q.push(node2->right);
}
}
}
// 把第2棵树合并到第1棵树上，所以返回的是第1棵树
return t1;
}
// 辅助函数：前序遍历打印二叉树
void preOrderPrint(TreeNode* root) {
if (root == nullptr)
return;
cout << root->val << " ";
preOrderPrint(root->left);
preOrderPrint(root->right);
}
int main() {
// 示例二叉树1
TreeNode* t1 = new TreeNode(1);
t1->left = new TreeNode(3);
t1->right = new TreeNode(2);
t1->left->left = new TreeNode(5);
// 示例二叉树2
TreeNode* t2 = new TreeNode(2);
t2->left = new TreeNode(1);
t2->right = new TreeNode(3);
t2->left->right = new TreeNode(4);
t2->right->right = new TreeNode(7);
// 合并两棵二叉树
TreeNode* mergedTree = mergeTrees(t1, t2);
// 打印合并后的二叉树
cout << "合并后的二叉树前序遍历结果: ";
preOrderPrint(mergedTree);
cout << endl;
return 0;
}原文地址：https://blog.csdn.net/linshantang/article/details/142592533
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！