【LeetCode 算法】Merge Two Binary Trees 合并二叉树
文章目录
- Merge Two Binary Trees 合并二叉树
- 问题描述:
- 分析
- 代码
- PreOrder DFS
- PreOrder
- Tag
Merge Two Binary Trees 合并二叉树
问题描述:
给你两棵二叉树: root1 和 root2 。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 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
相关文章:
【LeetCode 算法】Merge Two Binary Trees 合并二叉树
文章目录 Merge Two Binary Trees 合并二叉树问题描述:分析代码PreOrder DFSPreOrder Tag Merge Two Binary Trees 合并二叉树 问题描述: 给你两棵二叉树: root1 和 root2 。 想象一下,当你将其中一棵覆盖到另一棵之上时&#…...
系统架构设计师---2017年下午试题1分析与解答(试题五)
2017年下午试题1分析与解答 试题五 阅读以下关于Web系统架构设计的叙述,在答题纸上回答问题1至问题3. 【说明】 某电子商务企业因发展良好,客户量逐步增大,企业业务不断扩充,导致其原有的B2C商品交易平台己不能满足现有业务需求。因此,该企业委托某软件公司重新开发一套…...
el-table实现静态和动态合并单元格 以及内容显示的问题
实现效果图 <el-tablev-loading"loading":data"tableData"style"width: 100%":row-class-name"tableRowClassName"size"small"><el-table-column fixed label"序号" width"50"><el-tab…...
STM32F40X系列FSMC8路驱动LCD显示屏(LY-TFT30-39P-1509 芯片hx8352)
hx8352_8080_8bit_FMSC板级驱动 1.LCD相关1.1LCD参数1.2 LCD引脚1.3 LCD实物1.4 LCD引脚解释 2.接线关系3.STM32F40x基于FMSC16bit修改1)地址偏移2)删除多余GPIO3)修改FMSC的配置4)LCD初始化寄存器 3.板驱动程序4.运行结果 1.LCD相关 1.1LCD参数 LCD控制芯片&…...
小象课堂在线授课教育系统
此项目包含后端全部代码,前端包括后台和web界面的源码,数据库用的mysql,可当作课设或者毕设,还可写入自己的简历中 web界面展示: 前端后台界面展示: 用户管理 课程管理 内容配置 订单管理 系统管理 系统监控...
Android 电池容量获取
Android 原生设置电池容量是在 power_profile.xml 中配置,此文件默认在 frameworks 目录下,也可能有 overlay 目录文件。 <!-- This is the battery capacity in mAh (measured at nominal voltage) --><item name"battery.capacity"…...
无涯教程-Perl - tell函数
描述 此函数返回指定FILEHANDLE中读取指针的当前位置(以字节为单位)。如果省略FILEHANDLE,则它将返回上次访问的文件中的位置。 语法 以下是此函数的简单语法- tell FILEHANDLEtell返回值 此函数以字节为单位返回当前文件位置。 例 以下是显示其基本用法的示例代码,要检…...
【论文综述】Transformer 综述
中国科学院、东南大学等联合发表最新的视觉 Transformer 综述_中科院AI算法工程师的博客-CSDN博客 Transformer综述大全(1)【A Survey of Visual Transformers】_香博士的博客-CSDN博客 Transformer综述大全(2)【A Survey of Vi…...
博客摘录「 佛祖保佑,永无bug——springboot启动图案的修改方法」2023年6月8日
挺有意思的。佛祖保佑永无BUG 神兽护体 代码注释(各种版本)_风流 少年的博客-CSDN博客...
【JavaEE进阶】SpringBoot 日志
文章目录 一. 日志有什么用?二. 自定义日志打印1. 日志的使用与打印 三. 日志级别1. 日志级别有什么用?2. 日志级别的分类及使用 四. 日志持久化五. 更简单的日志输出---Lombok1. Lombok的使用2. lombok原理解释2.1 Lombok更多注解说明 一. 日志有什么用? 在Java中…...
conda - 调研介绍
介绍: conda 是一个工具, 也是一个可执行命令, 其核心功能是管理包与环境. conda 支持多种语言, 用来管理Python包是绰绰有余的. 这里注意区分conda和pip, pip命令可以在任何环境中安装Python包, 而conda则是在conda环境中安装任何语言包. 接触过的conda主要有miniconda与anac…...
keepalived集群
keepalived概述 keepalived软件就是通过vrrp协议来实现高可用功能。 VRRP通信原理 VRRP就是虚拟路由冗余协议,它的出现就是为了解决静态路由的单点故障。 VRRP是通过一种竞选一种协议机制来将路由交个某台VRRP路由器。 VRRP 用IP多播的方式(多播地…...
CentOS系统环境搭建(八)——CentOS7开机自动执行脚本(以MySQL为例)
CentOS7开机自动执行脚本 文章目录 CentOS7开机自动执行脚本第一步:新建一个脚本run.sh第二步:脚本添加可执行权限第三步:执行如下命令将/etc/rc.d/rc.local文标记为可执行文件第四步:打开/etc/rc.d/rc.local文件,在最…...
re学习(31)BUUCTF-xx(多层加密)
参考文章:【BUUCTF逆向 [2019红帽杯]xx】_nb_What_DG的博客-CSDN博客 re学习笔记(26)BUUCTF-re-[2019红帽杯]xx_Forgo7ten的博客-CSDN博客 还有B站 水番正文 IDA64位载入 shiftF12查看字符串 交叉引用找到关键代码 使用findcrypt插件找到…...
HDFS的小文件影响及解决办法
Hadoop Distributed File System (HDFS) 是用于存储和处理大规模数据的分布式文件系统。然而,HDFS 中的小文件可能会对系统性能和资源利用产生一些影响。下面是小文件对HDFS的影响以及处理方法的一些信息: 影响: 元数据开销: HDFS中的每个文件和目录都有相关的元数据(文件…...
【前端】husky 的使用
husky 是一个优化 git hooks 的 npm 库 Modern native Git hooks made easy 安装和使用 1.安装 npm install husky --save-dev 2. 初始化 npx husky install;官方文档的写法是在 package.json 中初始化,本质上还是执行了 npx husky install 指令 3. 添加…...
Spring系列篇 -- Bean的生命周期
目录 经典面试题目: 一,Bean的生命周期图 二,关于Bean的生命周期流程介绍: 三,Bean的单例与多例模式 总结: 前言:今天小编给大家带来的是关于Spring系列篇中的Bean的生命周期讲解。在了解B…...
分类预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元多输入分类预测
分类预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元多输入分类预测 目录 分类预测 | MATLAB实现BO-BiGRU贝叶斯优化双向门控循环单元多输入分类预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.Matlab实现BO-BiGRU贝叶斯优化双向门控循环单元多特征分…...
Linux权限系列--给普通用户添加某个命令的sudo权限
原文网址:Linux权限系列--给普通用户添加某个命令的sudo权限_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍Linux系统如何给普通用户添加某个命令的sudo权限。 使用场景 普通开发者可能需要sudo的命令: apt-get(经常要安装软件&#x…...
11-数据结构-栈和队列的应用(C语言)
栈和队列的应用 目录 栈和队列的应用 一、括号匹配(栈) 二、表达式的各种转换 (1)中缀转后缀(手工) (2)后缀转中缀表达式(手工) (3)中缀转后缀(栈) (4)中缀转后缀(树) (5)后缀表达式求值 (6)中缀表达式求值(栈…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
渗透实战PortSwigger靶场:lab13存储型DOM XSS详解
进来是需要留言的,先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码,输入的<>当成字符串处理回显到页面中,看来只是把用户输…...
