617. 合并二叉树 - Merge Two Binary Trees

🎯 问题描述（来源于LeetCode）

描述：
给定两棵二叉树 root1 和 root2，将它们合并成一棵新的二叉树。合并规则是：

如果两个节点重叠，则节点值相加作为合并后节点的新值。
如果其中一个节点为空，则直接使用非空节点作为合并后的节点。

说明：

合并后的树不需要是平衡二叉树，只需按照规则重建即可。
合并过程同步进行，不会修改原始树。

示例：

示例 1：

1 2	输入: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出: [3,4,5,5,4,null,7]

示例 2：

1 2	输入: root1 = [1], root2 = [1,2] 输出: [2,2]

💻 解题思路

思路1：递归前序遍历（同步合并）

算法步骤

递归终止条件：
- 如果 root1 为 None，则返回 root2。
- 如果 root2 为 None，则返回 root1。
- 这样可以处理其中一棵树节点为空的情况。
创建新节点：
- 新节点的值为两棵树当前节点值之和：root1.val + root2.val。
递归合并左右子树：
- 左子树：mergeTrees(root1.left, root2.left)
- 右子树：mergeTrees(root1.right, root2.right)
返回新节点：
- 将新节点（包含值和左右子树）返回给上层调用。

思路1：代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None or root2 is None:
            return root1 or root2
        return TreeNode(root1.val + root2.val, 
                        self.mergeTrees(root1.left, root2.left), 
                        self.mergeTrees(root1.right, root2.right))

思路1：📊 性能分析

复杂度验证

时间复杂度： $O(\min(n, m))$ ，其中 $n$ 和 $m$ 分别是两棵树的节点数。最坏情况下需要遍历较小树的所有节点。
空间复杂度： $O(\min(h_1, h_2))$ ，其中 $h_1, h_2$ 为树的高度。递归调用栈的深度取决于较矮树的高度，最坏情况（链状树）为 $O(\min(n, m))$ 。

思考

本题也可以原地修改其中一棵树（如 root1）来节省空间，但题目未禁止修改原树，且通常建议不修改输入。如果允许修改，可以复用 root1 节点，减少新节点创建。
注意 return root1 or root2 的简洁性：当 root1 非空时返回 root1，否则返回 root2，完美覆盖了空节点情况。
该递归方法相当于同时进行前序遍历，是二叉树上“同步操作”的典型应用。