难度: Easy
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2] 输出：[2,2]
提示：
[0, 2000] 内-104 <= Node.val <= 104运行时间: 76 ms
内存: 15.2 MB
# 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: TreeNode, root2: TreeNode) -> TreeNode:
def dfs(p, q):
if p is None and q is None:
return
elif p is None:
return q
elif q is None:
return p
else:
root = TreeNode(p.val + q.val)
root.left = dfs(p.left, q.left)
root.right = dfs(p.right, q.right)
return root
return dfs(root1, root2)
这个题解使用深度优先搜索（DFS）的方式来合并两棵二叉树。通过同时遍历两棵树的节点，将对应位置的节点值相加，构建出合并后的新二叉树。如果某个位置只在一棵树上有节点，则直接将该节点加入新树中；如果两棵树的对应位置都没有节点，则不进行操作。
时间复杂度: O(n)
空间复杂度: O(log(n))
# 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: TreeNode, root2: TreeNode) -> TreeNode:
def dfs(p, q):
# 如果两棵树的当前节点都为空，则返回空节点
if p is None and q is None:
return
# 如果树1的当前节点为空，则返回树2的当前节点
elif p is None:
return q
# 如果树2的当前节点为空，则返回树1的当前节点
elif q is None:
return p
else:
# 创建新节点，值为两棵树当前节点的值之和
root = TreeNode(p.val + q.val)
# 递归合并左子树
root.left = dfs(p.left, q.left)
# 递归合并右子树
root.right = dfs(p.right, q.right)
# 返回合并后的新节点
return root
# 从根节点开始合并两棵树
return dfs(root1, root2)
在合并两棵二叉树时，如果一个节点在一棵树中存在而在另一棵树中不存在，直接使用存在的节点不会改变原有树的结构，但它会导致合并后的树直接引用原树中的节点。这意味着，如果后续对合并后的树中的这些节点进行修改，可能会影响到原始树的节点，因为两棵树的节点是共享的。理想情况下，应该创建一个新的节点副本，以免原始树的结构或数据受到意外的修改。
如果两个树的高度差异很大，合并过程中的效率可能会受到影响。具体来说，递归调用将持续进行到较高的树的最深节点，这可能导致在较矮的树已经没有节点可供合并的情况下，递归仍在继续。这不仅影响合并的效率，还可能增加对系统资源的消耗，尤其是在栈空间的使用上。然而，这种情况下合并的结果通常是正确的，只是效率低下。
如果在合并过程中两个对应节点的值相加超出了int类型的范围，这会导致整数溢出。处理这种情况的方法可以有几种：1) 修改节点的数据类型为可以容纳更大数值的类型，如长整型（long）。2) 在进行加法操作之前检查值，如果预计会超出范围，则可以设置一个错误处理机制，例如返回一个特定的错误代码或抛出异常。3) 使用Python等语言的特性，它们支持大整数的自动处理，但在其他一些语言中，需要手动处理这些情况。