题目：
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

注意: 合并必须从两个树的根节点开始

思路一：

使用递归的方式进行遍历
直接覆盖t1节点，不用新建节点

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null)return root2;
        if(root2==null)return root1;
        root1.val=root1.val+root2.val;
        root1.left=mergeTrees(root1.left,root2.left);
        root1.right=mergeTrees(root1.right,root2.right);
        return root1;

    }
}

或者通过建立一个新节点

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
}

同理c语言
意思差不多

struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    if(!root1)return root2;
    if(!root2)return root1;
    root1->val=root1->val+root2->val;
    root1->left=mergeTrees(root1->left,root2->left);
    root1->right=mergeTrees(root1->right,root2->right);
    return root1;
}

思路二：

该思路主要参考如下链接
动画演示 递归+迭代 617.合并二叉树

使用迭代思想
利用辅助栈（广度优先遍历）

class Solution {
	public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
	//如果 t1和t2中，只要有一个是null，函数就直接返回
		if(t1==null || t2==null) {
			return t1==null? t2 : t1;
		}
		java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<TreeNode>();
		queue.add(t1);
		queue.add(t2);
		while(queue.size()>0) {
			TreeNode r1 = queue.remove();
			TreeNode r2 = queue.remove();
			r1.val += r2.val;
			//如果r1和r2的左子树都不为空，就放到队列中
			//如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
			if(r1.left!=null && r2.left!=null){
				queue.add(r1.left);
				queue.add(r2.left);
			}
			else if(r1.left==null) {
				r1.left = r2.left;
			}
			//对于右子树也是一样的
			if(r1.right!=null && r2.right!=null) {
				queue.add(r1.right);
				queue.add(r2.right);
			}
			else if(r1.right==null) {
				r1.right = r2.right;
			}
		}
		return t1;
	}
}