题解 | #合并二叉树#

//!recurience &c++
//step 1：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。
//step 2：使用三个辅助队列，第一个队列q用于暂存合并后的二叉树的层次遍历节点，第二个队列q1用于暂存t1的层次遍历节点，第三个队列q2用于暂存t2的层次遍历节点。
//step 3：两棵树同步层次遍历，先将根节点加入队列中，同时根节点优先合并。
//step 4：每次从队列分别弹出一个元素，判断分别二者的左右子节点是否存在，若是都存在，则相加合并，若是只存在一个则连接该存在的节点，若是都不存在则连接null。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

#include <queue>
class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        //非递归
        if (t1==NULL) {
            return t2;
        }
        if (t2==NULL) {
            return t1;
        }
        TreeNode* head=new TreeNode(t1->val+t2->val);
        queue<TreeNode*> q;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q.push(head);
        q1.push(t1);
        q2.push(t2);
        while(!q1.empty()||!q2.empty()){
            TreeNode *node=q.front(),*node1=q1.front(),*node2=q2.front();
            q.pop();
            q1.pop();
            q2.pop();
            TreeNode *left1=node1->left,*left2=node2->left,*right1=node1->right,*right2=node2->right;
            if (left1&&left2) {
                TreeNode *left=new TreeNode(left1->val+left2->val);
                node->left=left;
                q.push(left);
                q1.push(left1);
                q2.push(left2);
            
            }else if (left1) {
                node->left=left1;
                
            }else if (left2) {
                node->left=left2;
            }

            if (right1&&right2) {
                TreeNode *right=new TreeNode(right1->val+right2->val);
                node->right=right;
                q.push(right);
                q1.push(right1);
                q2.push(right2);
            
            }else if (right1) {
                node->right=right1;
                
            }else if (right2) {
                node->right=right2;
            }

        }
        return head;

        

    }
};