方法一：递归

1.解题思路

题意：
给定两颗二叉树，要求我们将两颗二叉树合并为一棵树。对于两棵树相同位置的非空节点，将结点权值相加，否则取非空结点替代。
分析：
同时遍历两棵树，并对其相同位置的结点合并权值

2.解法

我们可以想到，同时遍历两棵树，将其中一棵树节点权值加到另一棵树上即可。或新建一棵树，将同时遍历到的结点权值都赋值给新树结点。采用深度优先的前序，中序，后序或广度优先的层序都可，这里我们尝试采用先序解决。

3.具体代码

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL&&t2==NULL)return NULL;//当两棵树同时遍历到的结点都为空树则直接返回 
        else if(t1==NULL)return t2;//当两棵树同时遍历到的结点，一个是空结点，一个非空时，则返回非空结点
        else if(t2==NULL)return t1;
        t1->val+=t2->val;//当两棵树结点都为非空时，将结点权值之和赋给其中一棵树
        t1->left=mergeTrees(t1->left,t2->left);//递归左右子树
        t1->right=mergeTrees(t1->right,t2->right); 
        return t1;//返回合并的树
    }
};

4.时间复杂度和空间复杂度分析

时间复杂度：，n，m分别为初始两棵树的结点数目，我们的递归边界就是两棵树相同位置的结点有空结点即返回。所以，时间复杂度为两棵树结点数目中最小的结点数目。
空间复杂度：，递归深度同上，只访问了两树相同位置都非空的地方。

方法二：迭代

1.解题思路

迭代实现采用了广度优先遍历，只有两棵树相同位置的结点都不为空时，放入队列。每次访问队列时，取出两个元素计算权值和，并将子节点都不为空的结点入队。

2.解法

初始化，将两棵树根节点入队；
接着不断从队列取出两个元素，计算和后赋值给树1当前结点。接着访问左右子树，当两棵树对应子节点都不为空时，才将子结点入队，供下一次访问。或者在树1当前子结点为空的时候，将树2的对应位置子节点直接赋值给树1。

3.图解

图片说明

4.具体代码

class Solution {
public:
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        queue<TreeNode*>q;//保存结点权值
        q.push(t1);//将两棵树的根结点依次入队
        q.push(t2);
        while(!q.empty()){
            TreeNode* c1=q.front();q.pop();//取出队列中保存的两颗树的相同位置的结点
            TreeNode* c2=q.front();q.pop();
            c1->val+=c2->val;//权值之和赋值给树1
            //c1c2左子树都不为空，就将其加入队列，如果c1子树为空，则在c2非空的情况下用c2子树替代 
            if(c1->left!=NULL&&c2->left!=NULL){
                q.push(c1->left);
                q.push(c2->left);
            }else if(c1->left==NULL) c1->left=c2->left;
            //c1c2右子树都不为空，就将其加入队列，如果c1子树为空，则在c2非空的情况下用c2子树替代 
            if(c1->right!=NULL&&c2->right!=NULL){
                q.push(c1->right);
                q.push(c2->right);
            }else if(c1->right==NULL) c1->right=c2->right;            
        }
        return t1;//返回合并的树 
    }
};

5.时间复杂度和空间复杂度分析

时间复杂度：，同方法一，也是只访问两棵树相同位置的非空结点。
空间复杂度：，所用队列中仅仅将两棵树相同位置的非空结点入队。