思路：

题目的主要信息：

• 合并（相加）二叉树位置相同的结点
• 缺少的结点用另一棵树来补，若都缺则返回NULL

方法一：递归先序遍历

同时先序遍历两棵树即可完成。

具体做法：

首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。然后依据先序遍历的特点，根左右的顺序递归访问。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        //若只有一个结点返回另一个，两个都为NULL自然返回NULL
        if (t1 == NULL) 
            return t2;
        if (t2 == NULL)
            return t1;
        //根左右的方式递归
        TreeNode* head = new TreeNode(t1->val + t2->val);
        head->left = mergeTrees(t1->left, t2->left);
        head->right = mergeTrees(t1->right, t2->right);
        return head;
    }
};

复杂度分析：

• 时间复杂度：$O\left(min\right(n,m\left)\right)O(min(n,m))$O(min(n,m))，m和n分别为两棵树的结点树，当一个树访问完时，自然就连接上另一个树的结点，故只访问了小树的结点数。
• 空间复杂度：$O\left(min\right(n,m\left)\right)O(min(n,m))$O(min(n,m))，递归栈深度也同时间，只访问了小树的结点数。

方法二：非递归层次遍历

具体做法：

使用三个辅助队列，第一个队列q用于暂存合并后的二叉树的层次遍历结点，第二个队列q1用于暂存t1的层次遍历结点，第三个队列q2用于暂存t2的层次遍历结点。 层次遍历两棵树，判断分别二者的左右子结点是否存在，若是都存在，则相加合并，若是只存在一个则连接该存在的结点，若是都不存在则连接NULL。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
         //若只有一个结点返回另一个，两个都为NULL自然返回NULL
        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) { //两个左节点都存在
                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) {
                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 
                    node->right = right2;
            }
        }
        return head;
    }
};

复杂度分析：

• 时间复杂度：$O\left(min\right(n,m\left)\right)O(min(n,m))$O(min(n,m))，m和n分别为两棵树的结点树，当一个树访问完时，自然就连接上另一个树的结点，故只访问了小树的结点数。
• 空间复杂度：$O\left(min\right(n,m\left)\right)O(min(n,m))$O(min(n,m))，辅助队列同时间，只访问了小树的结点数。