2024.2.20力扣每日一题——从前序和中序遍历序列构建二叉树
2024.2.20
- 题目来源
- 我的题解
- 方法一 递归
- 方法二 迭代
题目来源
力扣每日一题;题序:105
我的题解
方法一 递归
- 前序特点:[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
- 中序特点:[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要在中序遍历中定位到根节点,那么就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。
这样以来,就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。
时间复杂度:O( n 2 n^2 n2) 。除了遍历节点,还需要扫描整个中序遍历的结果并找出根节点
空间复杂度:O(n)
public TreeNode buildTree(int[] preorder, int[] inorder) {return createTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
}
// mid 根所在的位置
// pR 对应前序结束的位置
// iL 对应中序开始的位置
// iR 对应中序结束的位置
public TreeNode createTree(int[] preorder,int[] inorder,int mid,int pR,int iL,int iR){if(mid>pR||iL>iR)return null;int val=preorder[mid];TreeNode root=new TreeNode(val);int index=find(inorder,val,iL,iR);// 左子树的节点数量int left=index-iL;// 右子树的节点数量int right=iR-index;
// 构建左子树需要的前序序列和中序序列 pre[mid,mid+left] in[iL,index-1] root.left=createTree(preorder,inorder,mid+1,mid+left,iL,index-1);
// 构建右子树需要的前序序列和中序序列 pre[mid+left+1,pR] in[index+1,iR] root.right=createTree(preorder,inorder,mid+left+1,pR,index+1,iR);return root;
}
//在中序序列中找寻与前序对应的值val所在的位置
public int find(int[] inorder,int val,int iL,int iR){int index=iL;for(int i=iL;i<=iR;i++){if(inorder[i]==val){index=i;}}return index;
}
在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,这样做需要频繁扫描,时间复杂度较高。可以考虑使用哈希表来帮助快速地定位根节点。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,就只需要 O(1)的时间对根节点进行定位了。
//哈希表优化版本
public TreeNode buildTree(int[] preorder, int[] inorder) {Map<Integer,Integer> map=new HashMap<>();//只需要遍历一次for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return createTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1,map);
}
public TreeNode createTree(int[] preorder,int[] inorder,int mid,int pR,int iL,int iR,Map<Integer,Integer> map){if(mid>pR||iL>iR)return null;int val=preorder[mid];TreeNode root=new TreeNode(val);//直接根据哈希表确定位置int index=map.get(val);int left=index-iL;int right=iR-index;root.left=createTree(preorder,inorder,mid+1,mid+left,iL,index-1,map);root.right=createTree(preorder,inorder,mid+left+1,pR,index+1,iR,map);return root;
}
方法二 迭代
看官方题解吧,没怎么弄明白
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
相关文章:
2024.2.20力扣每日一题——从前序和中序遍历序列构建二叉树
2024.2.20 题目来源我的题解方法一 递归方法二 迭代 题目来源 力扣每日一题;题序:105 我的题解 方法一 递归 前序特点:[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]中序特点:[ [左子树的中序遍历结果], 根节点…...
c++ 小游戏(2种)
目录 介绍 游戏1 游戏2 介绍 因为DEV C的编译环境较小,所以大部分的游戏代码都无法在此上运行,我收集了一部分摸鱼小游戏的源码,在此呈现,如果有能在DEV C上运行的我会先作声明: 游戏1 扫雷 #include<stdio.…...

电阻详解:定义、公式、影响因素及电阻器类型解析
电阻定义 电阻是指当电流通过导体时,导体对电流流动所呈现的阻碍作用的物理量。它是电路元件的一个基本参数,用于量化导体阻止电荷定向移动的能力。#电阻#的大小决定了通过导体的电流与两端电压之间的关系,遵循欧姆定律,即在恒定…...

LabVIEW动车组谐波分析与检测系统
LabVIEW动车组谐波分析与检测系统 随着中国高速铁路网络的快速发展,动车组数量和运行速度的不断提升,其产生的谐波问题对电网产生了不小的影响。基于图形化编程语言LabVIEW,开发了一套动车组谐波分析与检测系统,旨在实时监控与分…...
H5移动端 Vue3 + vue-virtual-scroller 实现长列表性能优化
文章目录 安装 vue-virtual-scroller引入📢注意事项使用基础使用上拉加载下拉刷新 移动端在渲染长列表时 大量dom节点的渲染和重绘重排会导致页面卡顿、滚动不流畅、设备耗电加快、影响移动设备电池寿命等性能问题 这里分享使用【虚拟滚动】方案进行长列表优化&…...
第20章-IP路由原理
目录 1. 概述 2. 路由表 3. 查表规则 4. 路由来源类型 5. 路由优先级 6. 路由的度量值 7. 路由器写表规则 1. 概述 1. 定义 路由器:异构网络互联机制; 路由:指导路由器如何进行数据发送的路径信息; 路由表:目的地址、下一跳、出接口等; 2. IP连通的条件 沿途的每…...

SBCFormer:能够在单板计算机上以每秒1帧的速度进行全尺寸ImageNet分类的轻量级网络
文章目录 摘要1、引言2、 相关工作2.1、用于移动设备的卷积网络2.2、移动设备上的ViT和CNN-ViT混合模型2.3、评估指标 3、CNN-ViT 混合模型在低端CPU上的应用3.1、设计原则3.2、SBCFormer的整体设计3.3、SBCFormer块3.4、改进的注意力机制 4、实验结果4.1、实验设置4.2、ImageN…...

【opencv】教程代码 —features2D(8)AKAZE 特征点匹配和图像拼接
graf1.png graf3.png <?xml version"1.0"?> <opencv_storage> <H13 type_id"opencv-matrix"><rows>3</rows><cols>3</cols><dt>d</dt><data>7.6285898e-01 -2.9922929e-01 2.2567123e02…...

ssm基于springboot的数字家庭亲子视频分享网站java+vue
本网站的模块主要分为前台展示模块和后台管理模块。 前台展示模块功能如下: 1)家庭照片模块 主要功能是对家庭照片的分类显示,如旅游、运动、生活、工作、学习等,每一类中的照片按时间轴展示出来。 2)家庭亲子视频模块…...
产品经理功法修炼(1)之自我管理
点击下载《产品经理功法修炼(1)之自我管理》 1. 前言 产品经理的能力修炼并非局限于某一技能的速成,而是需要全面参与到产品的整个生命周期中,通过不断的实践来逐步提升自己的各项能力。尽管在企业的日常运作中,我们不可能身兼数职去扮演每一个角色,但作为产品的核心负…...

2024年04月IDE流行度最新排名
点击查看最新IDE流行度最新排名(每月更新) 2024年04月IDE流行度最新排名 顶级IDE排名是通过分析在谷歌上搜索IDE下载页面的频率而创建的 一个IDE被搜索的次数越多,这个IDE就被认为越受欢迎。原始数据来自谷歌Trends 如果您相信集体智慧&am…...

17.应用负载压力测试
早些点,下午题考,最近几年出现的少; 备考较为简单;历年真题相似度高; 主要议题: 1.负载压力测试概述 注意这些测试细微的差别; 负载测试和压力测试的方法比较相似,但是目的不同&a…...
Gauss到底是不是国产数据库
华为GaussDB数据库深度解析 引言 在数字化转型的浪潮中,数据成为企业最宝贵的资产之一。如何高效地管理和利用这些数据,成为企业面临的一大挑战。数据库作为数据存储和管理的核心系统,其性能、安全性、可用性和扩展性等特性直接影响到企业的…...

spark sql执行引擎原理及配置
如果我们想要给上层开发人员配置好一个统一的sql开发界面,让他们统一通过sql开发即可,可通过spark中的thriftserver服务实现,与hive中的thriftserver类似,配置好该服务后,上层通过db client或者代码中通过jdbc连接即可…...

【C语言基础】:自定义类型(二) -->联合和枚举
文章目录 一、联合体1.1 联合体类型的声明1.2 联合体的特点1.3 相同成员的结构体和联合体对比1.4 联合体大小的计算1.5 联合体练习 二、枚举类型2.1 枚举类型的声明2.2 枚举的优点 书山有路勤为径,学海无涯苦作舟。 创作不易,宝子们!如果这篇…...
【授时防火墙】GPS北斗卫星授时信号安全防护装置系统
【授时防火墙】GPS北斗卫星授时信号安全防护装置系统 【授时防火墙】GPS北斗卫星授时信号安全防护装置系统 1、装置概述 卫星信号安全防护装置(以下简称“防护装置”)是一款专门针对卫星导航授时安全的设备。该设备能接收 BD 系统和 GPS 系统卫星信号&am…...
关于 MySQL 优化(详解)
文章目录 关于 MySQL 优化一、硬件方面的优化1、关于 CPU2、关于内存3、关于磁盘 二、MySQL 配置文件1、 default-time-zone8:002、interactive_timeout 1203、wait_timeout 1204、open_files_limit 102405、group_concat_max_len 1024006、usermysql7、character-set-serv…...

Hive详解(5)
Hive 窗口函数 案例 需求:连续三天登陆的用户数据 步骤: -- 建表 create table logins (username string,log_date string ) row format delimited fields terminated by ; -- 加载数据 load data local inpath /opt/hive_data/login into table log…...
阿里云效codeup如何执行github flow工作流
在阿里云效中执行 GitHub 工作流,实质上是在使用 Git 进行版本控制的过程中遵循 GitHub Flow 的原则。GitHub Flow 是一种简洁高效的工作流程,特别适用于追求快速迭代的团队。下面是在阿里云效中执行 GitHub 工作流的基本步骤: 1. 准备工作 …...

node.js的模块化 与 CommonJS规范
一、node.js的模块化 (1)什么是模块化? 将一个复杂的程序文件依据一定的规则拆分成为多个文件的过程就是模块化 在node.js中,模块化是指把一个大文件拆分成独立并且相互依赖的多个小模块,将每个js文件被认为单独的一个模块;模块…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...