import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public 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);
        head.left = mergeTrees(t1.left,t2.left);
        head.right = mergeTrees(t1.right,t2.right);

        return head;
    }
}

方法一：递归--先序遍历

递归出口：有一方为空则返回另一方。

递归主体：根据先序遍历，对当前节点操作，即建立一个新结点head，值为两个节点的值之和。

递归条件：先遍历两个节点的左子树，令新结点head的左指针指向向下递归的返回节点；再遍历两个节点的右子树，令新结点head的右指针指向它。

最后返回head；

方法二：非递归--队列层次遍历

利用队列的先进先出的特性，结合题目，需要同步访问两个子树，所以采用层次遍历。首先，若有一棵树为空则返回另一棵。然后生成新树的根节点，值为两个树的根节点的值之和，还需要定义三个队列用于存储新树和另外两个树将要访问的节点，再将三个根节点入队，循环中根据先左后右的顺序依次判断节点是否存在，进而做出对应的合入新树的操作具体看代码注释。由于在合入时需要知道前一节点，所以不能用当前节点作为遍历和判断条件，而应该将左右子节点进行判断，然后用当前节点连接新结点。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param t1 TreeNode类
     * @param t2 TreeNode类
     * @return TreeNode类
     */
    public 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 = new LinkedList<TreeNode>();
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q.offer(head);
        q1.offer(t1);
        q2.offer(t2);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            TreeNode left1 = node1.left;
            TreeNode left2 = node2.left;
            TreeNode right1 = node1.right;
            TreeNode right2 = node2.right;
            if (left1 != null || left2 != null) {
                //两个左节点都存在
                if (left1 != null && left2 != null) {
                    //创建合并的新结点
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    //新结点合入新树
                    node.left = left;
                    //左节点入队为下次访问子节点做准备
                    q.offer(left);
                    q1.offer(left1);
                    q2.offer(left2);
                } else if (left1 != null) {
                    //第一个树的左子树不为空，第二个树的左子树为空
                    node.left = left1;
                } else {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                //两个右节点都存在
                if (right1 != null && right2 != null) {
                    //创建合并的新结点
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    //新结点合入新树
                    node.right = right;
                    //右节点入队为下次访问子节点做准备
                    q.offer(right);
                    q1.offer(right1);
                    q2.offer(right2);
                } else if (right1 != null) {
                    //第一个树的右子树不为空，第二个树的右子树为空
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return head;
    }
}