617. 合并二叉树

617. 合并二叉树

解题思路
看了都是递归来递归去的，已经成为套公式题了，真的没劲的很，实际上迭代方式实现也很简单，可以自动动手画一个队列，亲自动手入队出队 很容易理解的，如果无法什么理解队列请到此结束。不要往下看了。

1创建一个队列，初始化是t1,t2的根节点加入队列
2 判断队列是否为空 2个一起出队
3 只有2棵树左孩子或者右孩子都不为空才入队 ，这样是为了保证每次可以出对是2个
4 因为我们是对t1数据修改 所以当前t1的左孩子或者右孩子为空 就把t2相对不为空的孩子嫁接过来

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func mergeTrees1(t1 *TreeNode, t2 *TreeNode) *TreeNode {
    if t1 == nil {
        return t2
    }
    if t2 == nil {
        return t1
    }
    t1.Val = t1.Val + t2.Val
    t1.Left = mergeTrees1(t1.Left, t2.Left)
    t1.Right = mergeTrees1(t1.Right, t2.Right)
    return t1
}
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
    if t1 == nil {
        return t2
    }
    if t2 == nil {
        return t1
    }
    queue := []*TreeNode{t1, t2}
    for len(queue) > 0 {
        n1 := queue[0]
        n2 := queue[1]
        n1.Val = n1.Val + n2.Val
        if n1.Left != nil && n2.Left != nil {
            queue = append(queue, n1.Left, n2.Left)
        } else if n1.Left == nil && n2.Left != nil {
            n1.Left = n2.Left
        }
        if n1.Right != nil && n2.Right != nil {
            queue = append(queue, n1.Right, n2.Right)
        } else if n1.Right == nil && n2.Right != nil {
            n1.Right = n2.Right
        }
        queue = queue[2:]
    }
    return t1
}
func main() {
    t1 := &TreeNode{Val: 1}
    t11 := &TreeNode{Val: 3}
    t1.Left = t11
    t12 := &TreeNode{Val: 2}
    t1.Right = t12
    t13 := &TreeNode{Val: 5}
    t11.Left = t13
    t2 := &TreeNode{Val: 2}
    t21 := &TreeNode{Val: 1}
    t2.Left = t21
    t22 := &TreeNode{Val: 3}
    t2.Right = t22
    t23 := &TreeNode{Val: 4}
    t21.Right = t23
    t24 := &TreeNode{Val: 7}
    t22.Right = t24
    printNode(mergeTrees(t1, t2)) //3 4 5 4 5 7
    fmt.Println()
    t3 := &TreeNode{Val: 1}
    t31 := &TreeNode{Val: 2}
    t3.Left = t31
    t32 := &TreeNode{Val: 3}
    t31.Left = t32
    t4 := &TreeNode{Val: 1}
    t41 := &TreeNode{Val: 2}
    t4.Right = t41
    t42 := &TreeNode{Val: 3}
    t41.Right = t42
    printNode(mergeTrees(t3, t4)) //2 2 3 2 3
}
func printNode(t1 *TreeNode) {
    if t1 == nil {
        return
    }
    fmt.Println(t1.Val)
    printNode(t1.Left)
    printNode(t1.Right)
}