当前位置: 首页 > 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;组件…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...