题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为?NULL 的节点将直接作为新二叉树的节点。
示例?1:
输入:?
?? ?Tree 1 ? ? ? ? ? ? ? ? ? ? Tree 2 ? ? ? ? ? ? ? ? ?
? ? ? ? ? 1 ? ? ? ? ? ? ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ?/ \ ? ? ? ? ? ? ? ? ? ? ? / \ ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? 3 ? 2 ? ? ? ? ? ? ? ? ? ? 1 ? 3 ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ?/ ? ? ? ? ? ? ? ? ? ? ? ? ? \ ? \ ? ? ? ? ? ? ? ? ? ? ?
? ? ? 5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4 ? 7 ? ? ? ? ? ? ? ? ?
输出:?
合并后的树:
?? ? ? ? 3
?? ? ? ?/ \
?? ? ? 4 ? 5
?? ? ?/ \ ? \?
?? ? 5 ? 4 ? 7
注意:?合并必须从两个树的根节点开始。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
解题思路
用BFS扫树，左边用队列q1来记录扫的结点，右边用队列q2来记录扫的结点，队列qr用来记录合并之后的结点。
在主函数中：
首先特判三种情况：
1.左树与右树都为空，直接return NULL
2.左树为空，右树非空，直接return 右树
3.左树非空，右树为空，直接return 左树
4.否则的话BFS扫一遍两棵树，然后将对应结点加起来，返回到新树res中。
在BFS函数中：
1.首先将三棵树的头结点都入队，res树的话，在主函数中定义了，取左右树根节点的和。root1入q1，root2入q2，res入qr。
2.用p1，p2，p3分别指向q1.front,q2.front,qr.front。
3.如果p1的左孩子和p2的左孩子都非空，那么pr的左孩子就是p1的左孩子+p2的左孩子。把他们分别入到自己的队列中，接着扫。
如果p1的右孩子和p2的右孩子都非空，那么pr的右孩子就是p1的右孩子+p2的右孩子。把他们入队，接着扫。
4.如果p1的左孩子为空，p2的左孩子非空，那么直接把pr的左孩子记为p2的左孩子。不用入队
如果p1的左孩子非空，p2的左孩子为空，那么直接把pr的左孩子记为p1的左孩子。不用入队
如果p1的右孩子为空，p2的右孩子非空，那么直接把pr的右孩子记为p2的右孩子。不用入队
如果p1的右孩子非空，p2的右孩子为空，那么直接把pr的右孩子记为p1的右孩子。不用入队
代码
/**
* 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:
void bfs(TreeNode* root1 , TreeNode* root2, TreeNode* &res){
queue<TreeNode*> q1; //用来记录root1的结点
queue<TreeNode*> q2;//用来记录root2的结点
queue<TreeNode*> qr;//用来记录res的结点
q1.push(root1); //头结点入队
q2.push(root2);//头结点入队
qr.push(res);//头结点入队
while(!q1.empty()&&!q2.empty()){
TreeNode* p1=q1.front(); //p1记录当前结点
TreeNode* p2=q2.front();//p2记录当前结点
TreeNode* pr=qr.front();//pr记录当前结点
q1.pop();//出队
q2.pop();//出队
qr.pop();//出队
if(p1->left!=NULL&&p2->left!=NULL){ //p1的左孩子和p2的左孩子都非空
pr->left=new TreeNode(p1->left->val+p2->left->val); //那他们的左孩子相加，并保存到pr的左孩子中
q1.push(p1->left); //入队
q2.push(p2->left); //入队
qr.push(pr->left); //入队
}
if(p1->right!=NULL&&p2->right!=NULL){ //p1的右孩子和p2的右孩子都非空
pr->right=new TreeNode(p1->right->val+p2->right->val);//那他们的右孩子相加，并保存到pr的右孩子中
q1.push(p1->right);//入队
q2.push(p2->right);//入队
qr.push(pr->right);//入队
}
if(p1->left==NULL&&p2->left!=NULL){ //p1的左孩子为空，p2的左孩子非空
pr->left=p2->left;//那么pr的左孩子就直接是p2的左孩子
}
if(p1->left!=NULL&&p2->left==NULL){//p1的左孩子非空，p2的左孩子为空
pr->left=p1->left;//那么pr的左孩子就直接是p1的左孩子
}
if(p1->right==NULL&&p2->right!=NULL){//p1的右孩子为空，p2的右孩子非空
pr->right=p2->right;//那么pr的右孩子就直接是p2的右孩子
}
if(p1->right!=NULL&&p2->right==NULL){//p1的右孩子非空，p2的右孩子为空
pr->right=p1->right;//那么pr的右孩子就直接是p1的右孩子
}
}
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==NULL&&root2==NULL){ //特判，左树和右树全空，直接return NULL
return NULL;
}
if(root1==NULL&&root2!=NULL){ //特判，左树为空，右树非空，直接return 右树
return root2;
}
if(root1!=NULL&&root2==NULL){ //特判，左树非空，右树为空，直接return 左树
return root1;
}
TreeNode* res=new TreeNode(root1->val+root2->val); //否则的话就要开始扫了，首先定义新树的头结点为前面的左树和右树的头结点的和
bfs(root1,root2,res); //然后bfs扫一遍，并且把结果返回给res
return res;
}
};
|