题目
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]提示：
- 两棵树中的节点数目在范围
[0, 2000]内 -104 <= Node.val <= 104
解答
- 通过深度优先遍历进行合并
如果有树为空，则直接返回另一个树；若两树都不为空，则新建一个节点，将对应的结点的值进行求和，递归调用函数，最终返回根结点。C++代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// 如果其中一个树为空，我们可以直接返回另一个树作为合并后的结果
if (root1 == nullptr) {
return root2;
}
if (root2 == nullptr) {
return root1;
}
// 创建一个新节点，值为两个树当前节点值的和
TreeNode *merged = new TreeNode(root1->val + root2->val);
// 递归地合并左子树和右子树
merged->left = mergeTrees(root1->left, root2->left);
merged->right = mergeTrees(root1->right, root2->right);
// 返回合并后的树
return merged;
}
};- 通过广度优先遍历实现合并
我们使用三个队列，q用于存储合并后的树节点，q1和q2分别用于存储两棵输入树的节点。
在每一轮循环中，我们弹出q、q1和q2的队首元素，分别表示合并后的树的当前节点、第一棵树的当前节点和第二棵树的当前节点。
然后，我们获取当前节点的左子节点和右子节点，并根据情况进行处理。
- 如果两棵树的左子节点都存在，我们创建一个合并后的左子节点，值为两个树的左子节点值之和，并将其连接到合并后的树的当前节点的左侧。同时，我们将合并后的左子节点、第一棵树的左子节点和第二棵树的左子节点分别入队列
q、q1和q2中。 - 如果只有第一棵树的左子节点存在，我们直接使用该节点，并将其连接到合并后的树的当前节点的左侧。
- 如果只有第二棵树的左子节点存在，我们直接使用该节点，并将其连接到合并后的树的当前节点的左侧。
对于右子节点，我们执行类似的逻辑。
最终，当队列q1和q2都为空时，表示已经遍历完两棵树的所有节点，此时合并过程完成，我们返回合并后的树的根节点。
这样，使用广度优先遍历的方式，我们可以合并两棵二叉树并返回合并后的结果。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
// 如果其中一个树为空，直接返回另一个树
if (t1 == NULL) {
return t2;
}
if (t2 == NULL) {
return t1;
}
// 创建一个新的节点，值为两个树当前节点值的和
TreeNode* merged = new TreeNode(t1->val + t2->val);
// 使用队列存储节点，初始时将根节点入队列
std::queue<TreeNode*> q;
q.push(merged);
std::queue<TreeNode*> q1;
std::queue<TreeNode*> q2;
q1.push(t1);
q2.push(t2);
while (!q1.empty() && !q2.empty()) {
// 弹出当前节点以及对应的两个输入树的节点
TreeNode* node = q.front();
q.pop();
TreeNode* node1 = q1.front();
q1.pop();
TreeNode* node2 = q2.front();
q2.pop();
// 获取当前节点的左子节点和右子节点
TreeNode* left1 = node1->left;
TreeNode* left2 = node2->left;
TreeNode* right1 = node1->right;
TreeNode* right2 = node2->right;
// 处理左子节点
if (left1 != NULL || left2 != NULL) {
if (left1 != NULL && left2 != NULL) {
// 如果两棵树的左子节点都存在，创建合并后的左子节点，并入队列
TreeNode* leftMerged = new TreeNode(left1->val + left2->val);
node->left = leftMerged;
q.push(leftMerged);
q1.push(left1);
q2.push(left2);
} else if (left1 != NULL) {
// 如果只有第一棵树的左子节点存在，直接使用该节点
node->left = left1;
} else if (left2 != NULL) {
// 如果只有第二棵树的左子节点存在，直接使用该节点
node->left = left2;
}
}
// 处理右子节点
if (right1 != NULL || right2 != NULL) {
if (right1 != NULL && right2 != NULL) {
// 如果两棵树的右子节点都存在，创建合并后的右子节点，并入队列
TreeNode* rightMerged = new TreeNode(right1->val + right2->val);
node->right = rightMerged;
q.push(rightMerged);
q1.push(right1);
q2.push(right2);
} else if (right1 != NULL) {
// 如果只有第一棵树的右子节点存在，直接使用该节点
node->right = right1;
} else if (right2 != NULL) {
// 如果只有第二棵树的右子节点存在
node->right = right2;
}
}
}
// 返回合并后的树
return merged;
}
};