当前位置: 首页 > news >正文

【LeetCode 算法】Merge Two Binary Trees 合并二叉树

文章目录

Merge Two Binary Trees 合并二叉树

问题描述:

给你两棵二叉树: root1root2

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

两棵树中的节点数目在范围 [ 0 , 2000 ] 内 − 1 0 4 < = N o d e . v a l < = 1 0 4 两棵树中的节点数目在范围 [0, 2000] 内\\ -10^4 <= Node.val <= 10^4 两棵树中的节点数目在范围[0,2000]104<=Node.val<=104

分析

目标是将2个树,进行覆盖,可以合并到第3个树上,也可以将tree2合并到tree1.

而且是要求相同的位置进行merge,所以必然要对树进行遍历。

其中最简单的就是前序递归,细节就不说了,all in code.

相对于递归的方法比较容易想到,迭代的实现方式也有很多,所以有点绕。

代码

PreOrder DFS

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;} root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}

时间复杂度 O ( m i n ( M + N ) O(min(M+N) O(min(M+N)

空间复杂度 O ( H ) O(H) O(H)

PreOrder

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null||root2==null){return root1==null?root2:root1;} Deque<TreeNode[]> queue = new ArrayDeque();queue.offerLast(new TreeNode[]{root1,root2});while(!queue.isEmpty()){TreeNode[] t = queue.pollLast();TreeNode p1 = t[0],p2 =t[1];p1.val+= p2.val;TreeNode l1 = p1.left,l2 = p2.left;TreeNode r1 = p1.right,r2 = p2.right; if(r1!=null&&r2!=null){queue.offerLast(new TreeNode[]{r1,r2});}if(l1!=null&&l2!=null){queue.offerLast(new TreeNode[]{l1,l2});}if(l1==null||l2==null){p1.left = l1==null? l2:l1;} if(r1==null||r2==null){                p1.right = r1==null? r2:r1;} } return root1;}

时间复杂度 O ( m i n ( M + N ) O(min(M+N) O(min(M+N)

空间复杂度 O ( H ) O(H) O(H)

Tag

Tree

DFS

http://www.lryc.cn/news/129246.html

相关文章:

  • 系统架构设计师---2017年下午试题1分析与解答(试题五)
  • el-table实现静态和动态合并单元格 以及内容显示的问题
  • STM32F40X系列FSMC8路驱动LCD显示屏(LY-TFT30-39P-1509 芯片hx8352)
  • 小象课堂在线授课教育系统
  • Android 电池容量获取
  • 无涯教程-Perl - tell函数
  • 【论文综述】Transformer 综述
  • 博客摘录「 佛祖保佑,永无bug——springboot启动图案的修改方法」2023年6月8日
  • 【JavaEE进阶】SpringBoot 日志
  • conda - 调研介绍
  • keepalived集群
  • CentOS系统环境搭建(八)——CentOS7开机自动执行脚本(以MySQL为例)
  • re学习(31)BUUCTF-xx(多层加密)
  • HDFS的小文件影响及解决办法
  • 【前端】husky 的使用
  • Spring系列篇 -- Bean的生命周期
  • 分类预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元多输入分类预测
  • Linux权限系列--给普通用户添加某个命令的sudo权限
  • 11-数据结构-栈和队列的应用(C语言)
  • uni-app自定义多环境配置,动态修改appid
  • 04 - 分离头指针情况、理解HEAD和branch
  • C#__基本特性和使用
  • mysql(3)
  • 阿里巴巴常用的12个后端开发工具
  • php base64转图片保存本地
  • unity物体移动至指定位置
  • 详解C#-static void Main(string[] args)
  • 中大许少辉博士《乡村振兴战略下传统村落文化旅游设计》中国建筑工业出版社八一付梓。
  • Matplotlib数据可视化(五)
  • Python爬虫——requests_post请求