合并二叉树

[编程题]合并二叉树

热度指数：59122 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
Tree 1

Tree 2

合并后的树为

数据范围：树上节点数量满足 $0 \le n \le 500$ ，树上节点的值一定在32位整型范围内。

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,3,2,5},{2,1,3,#,4,#,7}

输出

{3,4,5,5,4,#,7}

说明

如题面图

示例2

输入

{1},{}

输出

{1}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python2

牛客30511778号

#coding:utf-8
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 , t2 ):
        # write code here
        # 若只有一个节点返回另一个，两个都为NULL自然返回NULL
        if not t1: 
            return t2
        if not t2:
            return t1
        # 根左右的方式递归
        root = TreeNode(t1.val + t2.val)
        root.left = self.mergeTrees(t1.left, t2.left)
        root.right = self.mergeTrees(t1.right, t2.right)
        return root

发表于 2024-06-29 11:10:01 回复(0)