给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。示例 1:
代码：
//深度优先遍历 func mergeTrees(t1, t2 *TreeNode) *TreeNode { if t1 == nil { return t2 } if t2 == nil { return t1 } t1.Val += t2.Val //左子树进行merge t1.Left = mergeTrees(t1.Left, t2.Left) //右子数进行merge t1.Right = mergeTrees(t1.Right, t2.Right) return t1 } //广度优先搜索 //广度优先搜索需要借助队列 func mergeTrees(t1, t2 *TreeNode) *TreeNode { if t1 == nil { return t2 } if t2 == nil { return t1 } //合并节点值 merged := &TreeNode{Val: t1.Val + t2.Val} //队列 queue := []*TreeNode{merged} queue1 := []*TreeNode{t1} queue2 := []*TreeNode{t2} for len(queue1) > 0 && len(queue2) > 0 { node := queue[0] //queue 出队 queue = queue[1:] node1 := queue1[0] //queue1出队 queue1 = queue1[1:] node2 := queue2[0] queue2出队 queue2 = queue2[1:] left1, right1 := node1.Left, node1.Right left2, right2 := node2.Left, node2.Right if left1 != nil || left2 != nil { if left1 != nil && left2 != nil { left := &TreeNode{Val: left1.Val + left2.Val} node.Left = left //入队 queue = append(queue, left) queue1 = append(queue1, left1) queue2 = append(queue2, left2) } else if left1 != nil { node.Left = left1 } else { // left2 != nil node.Left = left2 } } if right1 != nil || right2 != nil { if right1 != nil && right2 != nil { right := &TreeNode{Val: right1.Val + right2.Val} node.Right = right queue = append(queue, right) queue1 = append(queue1, right1) queue2 = append(queue2, right2) } else if right1 != nil { node.Right = right1 } else { // right2 != nil node.Right = right2 } } } return merged }
参考地址：https://leetcode-cn.com/problems/merge-two-binary-trees/solution/he-bing-er-cha-shu-by-leetcode-solution/
