题解 | #合并二叉树#

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        if(!t1) return t2;
        if(!t2) return t1;
        TreeNode *p=t1,*q=t2;
        queue<pair<TreeNode*,TreeNode*>> qu;
        qu.emplace(p,q);
        p->val+=q->val;
        while(qu.size()){
            int n=qu.size();
            for(int i=0;i<n;i++){
                auto[I,J]=qu.front();
                qu.pop();
                if(I->left && J->left){//当前子节点都存在时，节点和给t1
                    I->left->val+=J->left->val;
                    qu.emplace(I->left,J->left);
                }
                else if(J->left){//只有t2子节点时，创建新节点给t1
                    TreeNode *s=(TreeNode*)malloc(sizeof(TreeNode));
                    s->val=J->left->val;
                    s->left=s->right=NULL;
                    I->left=s;
                    qu.emplace(I->left,J->left);
                }//只要t2没有左或右子节点，即使t1有，t1节点也不入队
                if(I->right && J->right){
                    I->right->val+=J->right->val;
                    qu.emplace(I->right,J->right);
                }
                else if(J->right){
                    TreeNode *s=(TreeNode*)malloc(sizeof(TreeNode));
                    s->val=J->right->val;
                    s->left=s->right=NULL;
                    I->right=s;
                    qu.emplace(I->right,J->right);
                }
            }
        }
        return t1;
    }
};