我要招人

去企业版

首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树

热度指数：52930 时间限制：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，点此查看相关信息

算法知识视频讲解

牛客题解官

发表于 2022-04-22 11:59:28

精华题解题目的主要信息：合并（相加）二叉树位置相同的节点缺少的节点用另一棵树来补，若都缺则返回NULL 举一反三：学习完本题的思路你可以解决如下题目： BM28. 二叉树的最大深度 BM29. 二叉树中和为某一值的路径（一） BM31. 对称的二叉树 BM33. 二叉树的镜像 BM36. 判断是不展开全文

Yexiaomo

发表于 2021-01-07 10:19:46

非常简单的代码^_^解题思路：两个节点的值求和并赋给t1 递归合并t1、t2的左右节点。 public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if(t1 == null) return t2; 展开全文

牛客289281343号

发表于 2020-09-23 16:43:37

解题思路：将两个节点的值求和并赋给t1，然后递归合并t1、t2的左右节点。 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode ri 展开全文

梁石页

发表于 2021-03-06 11:29:25

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。可以看到对每个结点的操作是类似的，就可以将问题拆解成小问题，故采取递归的解法。step1：编写对当前结点的操作，以t1为主树返回。 TreeNode* mergeTrees(Tr 展开全文

加油做题

发表于 2022-05-23 10:07:59

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; * * C语言声明定义全局变量请加上static，防止重复定义 */ /** * * @par 展开全文

已注销

发表于 2022-03-17 18:25:25

你一开始要想到数这种数据结构，怎么返回头节点，答案毋庸置疑递归递归的思想一般是从后往前，这个题目又要每两个值相加，还存在左右子树一个有一个没有的情况，所以递归的返回值一定是有的那个，你大概知道return t1 || t2,如果两个都有就递归相加。 function mergeTrees( t1 展开全文

ETO-ccc

发表于 2023-03-25 17:02:50

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @ 展开全文

牛客877483763号

发表于 2021-12-28 18:00:34

NC117 合并二叉树描述已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。数据范围：树上节点数量满足 0≤n≤500，树上节点的值一定在32位整型范围内。进阶：空间复杂度 O(1) ，时间复杂度 O(n) 思路：递归，展开全文