python coding with ChatGPT 打卡第19天| 二叉树：合并二叉树

作者：花生_TL007 | 2024-03-08 13:25:43

踩

合并二叉树

Key Points

将直接在 root1 上就地合并 root2，以避免额外的空间复杂度

视频讲解

一起操作两个二叉树

重点分析

方法一：
递归（修改root1）

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # 递归终止条件: 
        #  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None. 
        if not root1: 
            return root2
        if not root2: 
            return root1
        # 上面的递归终止条件保证了代码执行到这里root1, root2都非空. 
        root1.val += root2.val # 中
        root1.left = self.mergeTrees(root1.left, root2.left) #左
        root1.right = self.mergeTrees(root1.right, root2.right) # 右
        
        return root1 # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：
递归（创建新节点）

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    root = TreeNode(root1.val + root2.val)
    root.left = mergeTrees(root1.left, root2.left)
    root.right = mergeTrees(root1.right, root2.right)
    return root
1
2
3
4
5
6
7
8
9

方法三：
迭代法（修改root1）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    
    # 使用队列存储需要合并的节点对
    queue = [(root1, root2)]
    while queue:
        node1, node2 = queue.pop(0)
        
        # 如果两个节点都不为 None，则合并它们的值
        if node1 is not None and node2 is not None:
            node1.val += node2.val
            
            # 如果 node1 的左子节点为空，我们直接将 node2 的左子节点链接过来
            if not node1.left:
                node1.left = node2.left
            else:
                queue.append((node1.left, node2.left))
            
            # 对于右子节点执行相同的操作
            if not node1.right:
                node1.right = node2.right
            else:
                queue.append((node1.right, node2.right))
                
    return root1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

方法四：
迭代法（新建节点）

def mergeTrees(root1, root2):
    if not root1 and not root2:
        return None
    elif not root1:
        return TreeNode(root2.val, root2.left, root2.right)
    elif not root2:
        return TreeNode(root1.val, root1.left, root1.right)
    else:
        # 创建一个新节点，值为两个节点值的和
        newNode = TreeNode(root1.val + root2.val)
        
        # 使用队列存储节点对，以并行遍历两棵树
        queue = [(root1, root2, newNode)]
        
        while queue:
            node1, node2, new_node = queue.pop(0)
            
            # 处理左子节点
            if node1.left or node2.left:
                if node1.left and node2.left:
                    new_node.left = TreeNode(node1.left.val + node2.left.val)
                    queue.append((node1.left, node2.left, new_node.left))
                elif node1.left:
                    new_node.left = TreeNode(node1.left.val, node1.left.left, node1.left.right)
                else:  # node2.left
                    new_node.left = TreeNode(node2.left.val, node2.left.left, node2.left.right)
            
            # 处理右子节点
            if node1.right or node2.right:
                if node1.right and node2.right:
                    new_node.right = TreeNode(node1.right.val + node2.right.val)
                    queue.append((node1.right, node2.right, new_node.right))
                elif node1.right:
                    new_node.right = TreeNode(node1.right.val, node1.right.left, node1.right.right)
                else:  # node2.right
                    new_node.right = TreeNode(node2.right.val, node2.right.left, node2.right.right)
                    
        return newNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/210367

python coding with ChatGPT 打卡第19天| 二叉树：合并二叉树

合并二叉树

Key Points

相关题目

视频讲解

重点分析