一、问题描述

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

二、方案一：递归法

1、思路

递归是解决树相关问题的常用方法。对于这个问题，我们可以递归地合并两个树的节点。

• 如果两个节点都为空，返回空。
• 如果一个节点为空，返回另一个节点。
• 如果两个节点都不为空，创建一个新的节点，其值为两个节点值之和，然后递归地合并左右子树。

2、代码实现

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

3、复杂度分析

• 时间复杂度：O(min(m, n))，其中m和n分别是两个树的节点数。
• 空间复杂度：O(min(m, n))，递归栈的深度取决于两个树中较小的一个。

三、方案二：迭代法

1、思路

迭代法通常使用栈或队列来模拟递归过程。

• 使用队列来存储待合并的节点对。
• 遍历队列，对于每一对节点，执行合并操作。
• 如果两个节点都不为空，将它们的值相加，并将非空的左右子节点加入队列。

2、代码实现

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    queue := []*TreeNode{root1, root2}
    for len(queue) > 0 {
        node1, node2 := queue[0], queue[1]
        queue = queue[2:]
        if node2 == nil {
            continue
        }
        node1.Val += node2.Val
        if node1.Left == nil {
            node1.Left = node2.Left
        } else {
            queue = append(queue, node1.Left, node2.Left)
        }
        if node1.Right == nil {
            node1.Right = node2.Right
        } else {
            queue = append(queue, node1.Right, node2.Right)
        }
    }
    return root1
}

3、复杂度分析

• 时间复杂度：O(min(m, n))，其中m和n分别是两个树的节点数。
• 空间复杂度：O(min(m, n))，队列中最多包含两个树中较小的一个的所有节点。

四、总结

递归法和迭代法都能有效地解决这个问题。递归法代码更简洁，但迭代法在空间复杂度上可能更有优势，因为它不需要递归栈空间。具体使用哪种方法取决于个人偏好和具体问题的需求。