面试热题(前中序遍历构建树)
给定两个整数数组
preorder和inorder,其中preorder是二叉树的先序遍历,inorder是同一棵树的中序遍历,请构造二叉树并返回其根节点。

题目中是给定两个数组,一个是存放这颗树的前序遍历的数组,一个是存放这棵树的中序遍历的数组,解这道题的关键我们首先要知道树的前中序遍历分别指的是什么?它们两者之间到底存在着什么关系?解下来让我们一探究竟
前序遍历:

前序遍历的遍历顺序是中左右,先遍历自己,后遍历自己的左子树,最后再遍历自己的右子树,由上图已知该树的前序遍历为[3,9,20,15,7]
中序遍历:

中序遍历的遍历顺序是左中右,先遍历左子树,后遍历自己,最后再遍历自己的右子树,由上图已知该树的中序遍历为[9,3,15,20,7]

观看这两个数组,有没有发现什么特别的地方?

树是一种天然的递归结构,每棵子树也可以称为一棵独立的树,根据上图我们不难发现,数组中的元素是严格按照中左右的顺序填充的

根据上图我们不难发现,数组中的元素是严格按照中左右的顺序填充的
所以我们再来看这两个数组的特点:

我们已经得知了这两个数组中的相存的特点,接下来就可以撸代码了
- 我们要通过数组中的元素值得到该元素在数组中的索引为位置,所们先要使用Map结构的数据结构去对我们的中序遍历时的数据进行预处理
Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}
- 然后开始我们的构建函数dfs(前序数组,前序开始的位置,前序结束的位置,中序数组,中序开始的位置,中序结束的位置)
return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
- 递归时如果出先了开始位置比结束位置还要大的时候,这种情况肯定是不满足我们的条件的,所以直接抛出null就可以了
if(pStart>pEnd||iStart>iEnd){return null;}
- 通过前序遍历数组拿到我们相对根节点,然后通过map去查询我们中序数组中我们的相对根节点的索引index,因为我们的中序遍历是左中右,所以中序遍历中的index-iStart的长度就是我们相对子树的节点的个数
int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;
- 最后开始dfs,构造左右子树,这道题就完成了
// 不包括当前的根结点 前序取不到起点(左开右闭) 中序取不到终点(左闭右开)root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);// 左子树下一次递归的起点 root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);// 右子树下一次递归的起点
接下来上源码供大家参考:
Map<Integer,Integer> map=new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder==null||inorder==null){return null;}for(int i=0;i<inorder.length;i++){map.put(inorder[i],i);}return dfs(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}public TreeNode dfs(int[] preorder,int pStart,int pEnd,int[]inorder,int iStart,int iEnd){if(pStart>pEnd||iStart>iEnd){return null;}int val=preorder[pStart];TreeNode root=new TreeNode(val);int size=map.get(val);int length=size-iStart;root.left=dfs(preorder,pStart+1,pStart+length,inorder,iStart,size-1);root.right=dfs(preorder,pStart+length+1,pEnd,inorder,size+1,iEnd);return root;}
相关文章:
面试热题(前中序遍历构建树)
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 题目中是给定两个数组,一个是存放这颗树的前序遍历的数组,一个是存放这棵树的…...
美术:贴图
游戏模型制作流程,SP和BP根据情况来选择软件对UV进行处理 3Dmax 制作模型和动画(橘肉)RizomUV 对模型进行展UV(橘皮)Substance Painter 纹理手绘(给橘皮制定想要的皮肤)BodyPaint 3D 纹理手绘&a…...
[MAUI]模仿微信“按住-说话”的交互实现
今天使用这个控件,做一个模仿微信“按住-说话”的小功能,最终效果如下: 使用.NET MAUI实现跨平台支持,本项目可运行于Android、iOS平台。 创建页面布局 新建.NET MAUI项目,命名HoldAndSpeak MainPage.xaml中创建一个…...
windows开机运行jar
windows开机自启动jar包: 一、保存bat批处理文件 echo off %1 mshta vbscript:CreateObject("WScript.Shell").Run("%~s0 ::",0,FALSE)(window.close)&&exit java -jar E:\projects\ruoyi-admin.jar > E:\server.log 2>&1 &…...
使用DockerFile一键创建自定义linux开发环境
1,使用dcokerfile文件构建镜像,参考如下文件 # 使用ubuntu:20.04镜像作为基础 FROM ubuntu:20.04# 调整时区 ENV DEBIAN_FRONTENDnoninteractive TZAsia/Shanghai# build参数 ARG userxiang usergroupduo# 设置默认工作路径 WORKDIR /home/${user}# 拷贝…...
“深入探索JVM:解密Java虚拟机的工作原理“
标题:深入探索JVM:解密Java虚拟机的工作原理 摘要:本文将深入探索Java虚拟机(JVM)的工作原理,从字节码到实际执行过程,从内存管理到垃圾回收等方面进行解析,帮助读者更好地理解和优…...
【华为OD机试】数字最低位排序【2023 B卷|100分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 给定一个非空数组(列表) 起元素数据类型为整型 请按照数组元素十进制最低位从小到大进行排序 十进制最低位相同的元素,相对位置保持不变 当数组元素为负值时,十进制最低为等同于去除符号…...
【Odoo16前端源码分析】xml模板的加载
一、模板内容的来源 情况A,组件类的template属性,比如ActionContainer.template /* odoo/addons/web/static/src/webclient/actions/action_container.js */export class ActionContainer extends Component {setup() {..} } .. ActionContainer.templ…...
Open3D (C++) 计算矩阵的广义逆
目录 一、算法原理1、广义逆2、计算过程二、代码实现三、结果展示四、参考链接本文由CSDN点云侠原创,原文链接。爬虫网站自重,把自己当个人,爬些不完整的误导别人有意思吗???? 一、算法原理 1、广义逆 非方阵不存在逆,但是存在广义逆(伪逆)。对于一个矩阵...
11.物联网操作系统内存管理
一。STM32编译过程及程序组成 STM32编译过程 程序的组成、存储与运行 MDK生成的主要文件分析 1.STM32编译过程 1.源文件(Source code)--》目标文件(Object code) .c(C语言)通过armcc生成.o,.s(汇编&…...
举办活动发布会,如何得到媒体支持?
传媒如春雨,润物细无声,大家好,我是51媒体网胡老师。 举办活动发布会并得到媒体报道的支持是一个关键的宣传和推广手段。以下是一些建议,帮助你增加吸引媒体关注和报道的机会: 1. 策划新闻价值:确保你的发…...
1139 First Contact(unique函数,string.substr()函数)
PTA | 程序设计类实验辅助教学平台 用map套个set来实现邻接表(排序都免了) #include<bits/stdc.h> using namespace std; int n,m,k; string a,b; map<string,set<string>>mp; int main() {cin.tie(0);cin >> n >> m;fo…...
Python元编程-装饰器介绍、使用
目录 一、Python元编程装饰器介绍 二、装饰器使用 1. 实现认证和授权功能 2.实现缓存功能 3.实现日志输出功能 三、附录 1. logging.basicConfig介绍 2. 精确到毫秒,打印时间 方法一:使用datetime 方法二:使用time 一、Python元编程…...
python进程池的使用
进程池的创建 apply() apply()方法用于向进程池提交一个任务,并等待任务完成并返回结果。 apply_async() apply_async()方法用于向进程池提交一个异步任务(即无需等待任务完成),将任务加入到进程池的队列里,并立即…...
Dockerfile构建lamp镜像
1、构建目录 [rootdocker ~]# mkdir compose_lamp [rootdocker ~]# cd compose_lamp/ 2、编写Docekerfile [rootdocker compose_lamp]# vim Dockerfile #基础镜像 FROM centos:7#维护该镜像的用户信息 MAINTAINER Crushlinux <crushlinux163.com>#安装httpd RUN yum -…...
LeetCode724. 寻找数组的中心下标
题干 给你一个整数数组 nums ,请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。…...
【云计算 | Docker】Docker容器后台运行不了?entrypoint在作妖?
1. 问题 使用镜像alpine起个容器,使其保持后台运行,正常情况有如下的效果,可以发现容器保持运行状态。 [rootk8s-master helloWorld]# docker run -dit docker.io/alpine /bin/sh 8d39d7579d5e4f1a560aef16ba57ab5cae2506ea9105e21cbc0634…...
DAY02_Spring第三方资源配置管理Spring容器Spring注解开发Spring整合Mybatis和Junit
目录 一 第三方资源配置管理1 管理DataSource连接池对象问题导入1.1 管理Druid连接池1.2 管理c3p0连接池 2 加载properties属性文件问题导入2.1 基本用法2.2 配置不加载系统属性2.3 加载properties文件写法 二 Spring容器1 Spring核心容器介绍问题导入1.1 创建容器1.2 获取bean…...
烘焙小程序蛋糕店烘焙店源码点心店小程序源码
本系统开发使用JAVA技术栈开发 使用uniapp技术栈 支持微信小程序 ,对接打印机,对接第三方同城跑腿平台 用户端使用:uniapp 管理端使用:vueelementui 后台服务使用:springbootjpa...
HarmonyOS 开发基础(五)对用户名做点啥
一、实现用户名检验 条件渲染 、生命周期 1.规定用户名长度 2.限定使用的数字及字母(涉及正则表达) // 导出方式直接从文件夹 import MyInput from "../common/commons/myInput" Entry Component /* 组件可以基于struct实现,组件…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
Android写一个捕获全局异常的工具类
项目开发和实际运行过程中难免会遇到异常发生,系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler,它是Thread的子类(就是package java.lang;里线程的Thread)。本文将利用它将设备信息、报错信息以及错误的发生时间都…...
Linux-进程间的通信
1、IPC: Inter Process Communication(进程间通信): 由于每个进程在操作系统中有独立的地址空间,它们不能像线程那样直接访问彼此的内存,所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...
