题目链接：LeetCode 617. 合并二叉树

题意：

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。
合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

解题思路：

递归法

直接递归法，根据题意模拟即可。

递归遍历两个树，遍历对应的节点，如果两个节点都存在，则新节点就是原两个节点的和，否则新节点就是原存在的那个节点。

代码：

//将 root2 合并到 root1 上
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    //情况1：如果两个树都为空，直接返回空
    if root1 == nil && root2 == nil {
        return nil
    } 
    //情况2：如果树1为空，树2不为空，返回树2
    if root1 == nil && root2 != nil{
        return root2
    }
    //情况3：两棵树都不空
    if root1 != nil  && root2 != nil{
        root1.Val = root1.Val + root2.Val
        root1.Left = mergeTrees(root1.Left,root2.Left)
        root1.Right = mergeTrees(root1.Right,root2.Right)
    }
    return root1
}

迭代法

本题要遍历两棵树，其实和遍历一棵树是一样的，采用层序遍历的方式进行迭代遍历

// 迭代版本
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    queue := make([]*TreeNode,0)
    if root1 == nil{
        return root2
    }
    if root2 == nil{
        return root1
    }
    queue = append(queue,root1)
    queue = append(queue,root2)

    for size := len(queue); size>0; size=len(queue) {
        node1 := queue[0]
        queue = queue[1:]
        node2 := queue[0]
        queue = queue[1:]
        node1.Val += node2.Val
        // 左子树都不为空
        if node1.Left != nil && node2.Left != nil {
            queue = append(queue,node1.Left)
            queue = append(queue,node2.Left)
        }
        // 右子树都不为空
        if node1.Right !=nil && node2.Right !=nil {
            queue = append(queue, node1.Right)
            queue = append(queue, node2.Right)
        }
        // 树 1 的左子树为 nil，直接接上树 2 的左子树
        if node1.Left == nil {
            node1.Left = node2.Left
        }
        // 树 1 的右子树为 nil，直接接上树 2 的右子树
        if node1.Right == nil {
            node1.Right = node2.Right
        }
    }
    return root1
}