首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树
  • 热度指数：59122 时间限制：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，点此查看相关信息
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-22 11:59:28
精华题解 题目的主要信息： 合并（相加）二叉树位置相同的节点 缺少的节点用另一棵树来补，若都缺则返回NULL 举一反三： 学习完本题的思路你可以解决如下题目： BM28. 二叉树的最大深度 BM29. 二叉树中和为某一值的路径（一） BM31. 对称的二叉树 BM33. 二叉树的镜像 BM36. 判断是不 展开全文
去ta的博客 赞 (11) 回复(1) 收起
头像 Yexiaomo
发表于 2021-01-07 10:19:46
非常简单的代码^_^解题思路： 两个节点的值求和并赋给t1 递归合并t1、t2的左右节点。 public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if(t1 == null) return t2; 展开全文
去ta的博客 赞 (60) 回复(3) 收起
头像 牛客289281343号
发表于 2020-09-23 16:43:37
解题思路：将两个节点的值求和并赋给t1，然后递归合并t1、t2的左右节点。 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode ri 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 加油做题
发表于 2022-05-23 10:07:59
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; * * C语言声明定义全局变量请加上static，防止重复定义 */ /** * * @par 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 已注销
发表于 2022-03-17 18:25:25
你一开始要想到数这种数据结构，怎么返回头节点，答案毋庸置疑递归 递归的思想一般是从后往前，这个题目又要每两个值相加，还存在左右子树一个有一个没有的情况，所以递归的返回值一定是有的那个，你大概知道return t1 || t2,如果两个都有就递归相加。 function mergeTrees( t1 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 ETO-ccc
发表于 2023-03-25 17:02:50
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 吱吱1111111
发表于 2024-09-22 17:53:20
看到大部分题解都用的递归，这里放一个用队列的思路 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客877483763号
发表于 2021-12-28 18:00:34
NC117 合并二叉树 描述 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。 数据范围：树上节点数量满足 0≤n≤500，树上节点的值一定在32位整型范围内。 进阶：空间复杂度 O(1) ，时间复杂度 O(n) 思路：递归， 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 wuqg5518
发表于 2021-10-22 14:57:56
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Sol 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 jing_zhong
发表于 2021-09-01 10:31:14
题目描述：已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：两颗二叉树是:*Tree 1 * 1 / \ 3 2 / 5 Tree 2 2 / \ 1 3 \ \ 4 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客962918465号
发表于 2024-10-20 20:17:49
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

合并二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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