题目链接

题解

1. 合并二叉树
2. 动画演示 递归+迭代 617.合并二叉树

思路

代码

# 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:
    ### 0202 DFS（72 ms，15.6 MB）
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1: return t2
        if not t2: return t1

        node = TreeNode(t1.val + t2.val)
        node.left = self.mergeTrees(t1.left, t2.left)
        node.right = self.mergeTrees(t1.right, t2.right)

        return node

    ### 0202 DFS + 原地变换（88 ms，15.5 MB）
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        def dfs(t1, t2):
            if not t1: return t2
            if not t2: return t1

            t1.val += t2.val
            t1.left = dfs(t1.left, t2.left)
            t1.right = dfs(t1.right, t2.right)

            return t1
        
        return dfs(t1, t2)

    ### 0202 BFS + 原地变换（68 ms，15.3 MB）
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1: return t2
        if not t2: return t1

        q = [(t1, t2)]

        while q:
            node1, node2 = q.pop(0)

            if node1 and node2:
                node1.val += node2.val
            
            if node1.left and node2.left:
                q.append((node1.left, node2.left))
            if node1.right and node2.right:
                q.append((node1.right, node2.right))

            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right

        return t1