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

面试热题(前中序遍历构建树)

       给定两个整数数组 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 &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 题目中是给定两个数组&#xff0c;一个是存放这颗树的前序遍历的数组&#xff0c;一个是存放这棵树的…...

美术:贴图

游戏模型制作流程&#xff0c;SP和BP根据情况来选择软件对UV进行处理 3Dmax 制作模型和动画&#xff08;橘肉&#xff09;RizomUV 对模型进行展UV&#xff08;橘皮&#xff09;Substance Painter 纹理手绘&#xff08;给橘皮制定想要的皮肤&#xff09;BodyPaint 3D 纹理手绘&a…...

[MAUI]模仿微信“按住-说话”的交互实现

今天使用这个控件&#xff0c;做一个模仿微信“按住-说话”的小功能&#xff0c;最终效果如下&#xff1a; 使用.NET MAUI实现跨平台支持&#xff0c;本项目可运行于Android、iOS平台。 创建页面布局 新建.NET MAUI项目&#xff0c;命名HoldAndSpeak MainPage.xaml中创建一个…...

windows开机运行jar

windows开机自启动jar包&#xff1a; 一、保存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&#xff0c;使用dcokerfile文件构建镜像&#xff0c;参考如下文件 # 使用ubuntu:20.04镜像作为基础 FROM ubuntu:20.04# 调整时区 ENV DEBIAN_FRONTENDnoninteractive TZAsia/Shanghai# build参数 ARG userxiang usergroupduo# 设置默认工作路径 WORKDIR /home/${user}# 拷贝…...

“深入探索JVM:解密Java虚拟机的工作原理“

标题&#xff1a;深入探索JVM&#xff1a;解密Java虚拟机的工作原理 摘要&#xff1a;本文将深入探索Java虚拟机&#xff08;JVM&#xff09;的工作原理&#xff0c;从字节码到实际执行过程&#xff0c;从内存管理到垃圾回收等方面进行解析&#xff0c;帮助读者更好地理解和优…...

【华为OD机试】数字最低位排序【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 给定一个非空数组(列表) 起元素数据类型为整型 请按照数组元素十进制最低位从小到大进行排序 十进制最低位相同的元素,相对位置保持不变 当数组元素为负值时,十进制最低为等同于去除符号…...

【Odoo16前端源码分析】xml模板的加载

一、模板内容的来源 情况A&#xff0c;组件类的template属性&#xff0c;比如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.源文件&#xff08;Source code&#xff09;--》目标文件&#xff08;Object code&#xff09; .c(C语言)通过armcc生成.o&#xff0c;.s&#xff08;汇编&…...

举办活动发布会,如何得到媒体支持?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 举办活动发布会并得到媒体报道的支持是一个关键的宣传和推广手段。以下是一些建议&#xff0c;帮助你增加吸引媒体关注和报道的机会&#xff1a; 1. 策划新闻价值&#xff1a;确保你的发…...

1139 First Contact(unique函数,string.substr()函数)

PTA | 程序设计类实验辅助教学平台 用map套个set来实现邻接表&#xff08;排序都免了&#xff09; #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. 精确到毫秒&#xff0c;打印时间 方法一&#xff1a;使用datetime 方法二&#xff1a;使用time 一、Python元编程…...

python进程池的使用

进程池的创建 apply() apply()方法用于向进程池提交一个任务&#xff0c;并等待任务完成并返回结果。 apply_async() apply_async()方法用于向进程池提交一个异步任务&#xff08;即无需等待任务完成&#xff09;&#xff0c;将任务加入到进程池的队列里&#xff0c;并立即…...

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 &#xff0c;请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标&#xff0c;其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端&#xff0c;那么左侧数之和视为 0 &#xff0c;因为在下标的左侧不存在元素。…...

【云计算 | Docker】Docker容器后台运行不了?entrypoint在作妖?

1. 问题 使用镜像alpine起个容器&#xff0c;使其保持后台运行&#xff0c;正常情况有如下的效果&#xff0c;可以发现容器保持运行状态。 [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技术栈 支持微信小程序 &#xff0c;对接打印机&#xff0c;对接第三方同城跑腿平台 用户端使用&#xff1a;uniapp 管理端使用&#xff1a;vueelementui 后台服务使用&#xff1a;springbootjpa...

HarmonyOS 开发基础(五)对用户名做点啥

一、实现用户名检验 条件渲染 、生命周期 1.规定用户名长度 2.限定使用的数字及字母&#xff08;涉及正则表达&#xff09; // 导出方式直接从文件夹 import MyInput from "../common/commons/myInput" Entry Component /* 组件可以基于struct实现&#xff0c;组件…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...