题解 | 合并二叉树

合并二叉树的核心思想是同时遍历两棵树的对应节点，若节点都存在则值相加，否则直接取非空节点作为结果。该操作可通过递归或迭代实现。

（一）递归法（前序遍历）

步骤：

1、终止条件： 若 t1 为空，返回 t2； 若 t2 为空，返回 t1。

2、处理当前节点： 将 t1.val += t2.val。

3、递归处理左右子树： t1.left = mergeTrees(t1.left, t2.left)

t1.right = mergeTrees(t1.right, t2.right)

4、返回合并后的 root1。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here DFS
        if not t1:
            return t2
        if not t2:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left,t2.left)
        t1.right = self.mergeTrees(t1.right,t2.right)
        return t1

该方法简洁高效，直接在原树上修改，节省空间。

（二）迭代法（队列层序遍历）

步骤：

1、若有一棵树为空，直接返回另一棵。

2、使用队列存储成对节点 (node1, node2)。

3、每次出队一对节点： 将 node1.val += node2.val。 若两者左子节点都存在，入队；否则若 node1.left 为空则赋值为 node2.left。 同理处理右子节点。

4、返回修改后的 root1。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param t1 TreeNode类 
# @param t2 TreeNode类 
# @return TreeNode类
#
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here BFS
        if not t1:
            return t2
        if not t2:
            return t1
        s = [(t1,t2)]
        while s:
            p = s.pop()
            p[0].val += p[1].val
            if p[0].left and p[1].left:
                s += [(p[0].left,p[1].left)]
            elif not p[0].left:
                p[0].left = p[1].left
            if p[0].right and p[1].right:
                s += [(p[0].right,p[1].right)]
            elif not p[0].right:
                p[0].right = p[1].right
        return t1

迭代法适合避免深递归导致的栈溢出。

建议：数据量小可用递归，数据量大或树深时推荐迭代。