[数据结构与算法]LeetCode 617.合并二叉树 C++

题目描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为?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;
    }
};