首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树
  • 热度指数：59244 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：
两颗二叉树是:
                                                                    Tree 1


                                                                        Tree 2

                                                                    合并后的树为
数据范围：树上节点数量满足 ，树上节点的值一定在32位整型范围内。
进阶：空间复杂度 ，时间复杂度
示例1

输入

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

输出

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

说明

如题面图
示例2

输入

{1},{}

输出

{1}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python3
AntonHan头像 AntonHan 
# 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
        if not t1:
            return t2
        if not t2:
            return t1
        head = TreeNode(t1.val + t2.val)
        head.left, head.right = self.mergeTrees(t1.left, t2.left), self.mergeTrees(t1.right, t2.right)
        return head

编辑于 2024-02-12 18:43:56 回复(0)
Python3
可道非常道头像 可道非常道 
# 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
        if not t1:
            return t2
        if not t2:
            return t1
        
        merged = TreeNode(t1.val + t2.val)
        merged.left = self.mergeTrees(t1.left, t2.left)
        merged.right = self.mergeTrees(t1.right, t2.right)
        
        return merged

发表于 2023-10-16 14:33:07 回复(0)
Python3
牛客429226965号头像 牛客429226965号
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        def dfs(tree1, tree2):
            if tree1 == None and tree2 != None:
                return  tree2
            if tree1 == None and tree2 == None:
                return None
            if tree1 != None and tree2 == None:
                return  tree1
            tree1.val = tree1.val + tree2.val
            tree1.left = dfs(tree1.left, tree2.left)
            tree1.right = dfs(tree1.right, tree2.right)
            return tree1
           
        return dfs(t1,t2)
发表于 2023-08-10 10:32:42 回复(0)
Python3
danspace头像 danspace 
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        # write code here
        if t1 is None and t2 is None:
            return None 
        if t1 is None:
            return t2 
        if t2 is None:
            return t1 
        t1.val += t2.val 
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

发表于 2023-04-26 21:49:26 回复(0)
Python3
牛客1217718号头像 牛客1217718号
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        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
发表于 2022-10-03 12:19:27 回复(0)
Python3
JianYue头像 JianYue 
# 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:
        if t1 is None&nbs***bsp;t2 is None:
            if t1:
                return t1
            else:
                return t2
        left = self.mergeTrees(t1.left, t2.left)
        right = self.mergeTrees(t1.right, t2.right)
        root = TreeNode(t1.val + t2.val)
        root.left = left
        root.right = right
        return root

发表于 2022-09-17 10:38:11 回复(0)
提交观点

问题信息

树
上传者：牛客332641号
难度：
6条回答 5680浏览

热门推荐

通过挑战的用户

查看代码

相关试题

合并二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号