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

       给定两个整数数组 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;}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/81802.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

让三驾马车奔腾:华为如何推动空间智能化发展?

上个月&#xff0c;国务院常务会议审议通过了《关于促进家居消费的若干措施》&#xff0c;其中明确提出了“推动单品智能向全屋智能发展创新培育智能消费”“开展数字家庭建设试点”等推动全屋智能拼配发展的建议与方案。 可以说&#xff0c;以整屋为单位的空间智能品类&#x…

【2.1】Java微服务: Nacos的使用

目录 Nacos介绍 Nacos安装 下载和安装 修改端口 启动 服务注册与发现 导入Nacos管理依赖 导入服务依赖 配置Nacos的服务地址 启动服务&#xff0c;查看已注册的服务 服务分级存储模型 分级存储模型介绍 具体结构 配置实例集群 同集群优先的负载均衡策略 服务权重配置…

安防监控视频汇聚EasyCVR平台的FLV视频流在VLC中无法播放的原因排查

众所周知&#xff0c;TSINGSEE青犀视频汇聚平台EasyCVR可支持多协议方式接入&#xff0c;包括主流标准协议国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。在视频流的处理与分发上&#xff0c;视频监控…

开发中的花样玩法(前端打工人须知)

一、关于vue使用vant的van-popup&#xff0c;子元素设定固定定位失效问题。 position: fixed; 原因是该组件使用了transform导致&#xff0c;父元素使用了transform会导致子元素在使用固定定位时失效&#xff0c;解决方法就是把要设置固定定位的子元素放在跟组件平级的位置&…

Java8 list多属性去重

大家好&#xff0c;我是三叔&#xff0c;很高兴这期又和大家见面了&#xff0c;一个奋斗在互联网的打工人。 在 Java 开发中&#xff0c;我们经常会面临对 List 中的对象属性去重的需求。然而&#xff0c;当需要根据多个属性来进行去重时&#xff0c;情况会稍微复杂一些。本篇…

STL模型修复权威指南【3D打印】

设计师和工程师通常需要软件来调整、修复和最终确定 3D 打印的 3D 模型。 幸运的是&#xff0c;手动网格编程的时代早已一去不复返了。 推荐&#xff1a;用 NSDT设计器 快速搭建可编程3D场景。 如今&#xff0c;有一系列专用工具可提供自动和手动 STL 修复功能。 自动向导足以满…

【Hystrix技术指南】(1)基本使用和配置说明

这世间许多事物皆因相信而存在&#xff0c;所以人们亲手捏出了泥菩萨&#xff0c;却选择坚定的去信仰它。 分布式系统的规模和复杂度不断增加&#xff0c;随着而来的是对分布式系统可用性的要求越来越高。在各种高可用设计模式中&#xff0c;【熔断、隔离、降级、限流】是经常被…

typora的使用

typora的使用 当出现 就会出现黄色 command option t &#xff1a;就会出现表格

W5500-EVB-PICO作为TCP Client 进行数据回环测试(五)

前言 上一章我们用W5500-EVB-PICO开发板通过DNS解析www.baidu.com&#xff08;百度域名&#xff09;成功得到其IP地址&#xff0c;那么本章我们将用我们的开发板作为客户端去连接服务器&#xff0c;并做数据回环测试&#xff1a;收到服务器发送的数据&#xff0c;并回传给服务器…

数据结构---跳表

目录标题 为什么会有跳表跳表的原理跳表的模拟实现准备工作find函数insert函数erase函数 测试效率比较 为什么会有跳表 在前面的学习过程中我们学习过链表这个容器&#xff0c;这个容器在头部和尾部插入数据的时间复杂度为O(1)&#xff0c;但是该容器存在一个缺陷就是不管数据…

linux学习——Redis基础

目录 一、noSQL 类型 特点及应用场景 二、Redis 三、安装方式 编译安装 rpm安装 四、目录结构 /etc/redis.conf 五、Redis命令 六、本地登录和远程登录 本地登录 远程登录 七、数据库操作 帮助信息 库操作 数据操作 八、Redis持久化 一、RDB类型 二、AOF模式 一…

点击下一页时表格的序号连接上一页的序号

项目场景&#xff1a; 提示&#xff1a;这里简述项目相关背景&#xff1a; 问题描述 提示&#xff1a;这里描述项目中遇到的问题&#xff1a; 平时的分页都是每页的第一条都是"1"&#xff0c;并不会连接上一页的序号&#xff0c;现在需要&#xff0c;每页都要连接…

WPF上位机8——C#与MySQL

ADO.NET 数据库连接 数据插入、删除、更改 数据查询 带单个参数 带多个参数 using MySql.Data.MySqlClient; using System; using System.Collections.Generic; using System.Configuration; using System.Linq; using System.Text; using System.Threading.Tasks;namespace Wp…

【深度学习_TensorFlow】感知机、全连接层、神经网络

写在前面 感知机、全连接层、神经网络是什么意思&#xff1f; 感知机&#xff1a; 是最简单的神经网络结构&#xff0c;可以对线性可分的数据进行分类。 全连接层&#xff1a; 是神经网络中的一种层结构&#xff0c;每个神经元与上一层的所有神经元相连接,实现全连接。 神经…

剑指Offer12.矩阵中的路径 C++

1、题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻”单元格是那些水平…

分享一个计算器

先看效果&#xff1a; 再看代码&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>计算器</title><style>* {box-sizing: border-box;}body…

k8s学习day03

第五章 Pod详解 本章节将详细介绍Pod资源的各种配置&#xff08;yaml&#xff09;和原理。 Pod介绍 Pod结构 每个Pod中都可以包含一个或者多个容器&#xff0c;这些容器可以分为两类&#xff1a; 用户程序所在的容器&#xff0c;数量可多可少 Pause容器&#xff0c;这是每个…

ChatGPT 作为 Python 编程助手

推荐&#xff1a;使用 NSDT场景编辑器 助你快速搭建可编辑的3D应用场景 简单的数据处理脚本 我认为一个好的起点是某种数据处理脚本。由于我打算让 ChatGPT 之后使用各种 Python 库编写一些机器学习脚本&#xff0c;这似乎是一个合理的起点。 目标 首先&#xff0c;我想尝试…

常用开源的弱口令检查审计工具

常用开源的弱口令检查审计工具 1、SNETCracker 1.1、超级弱口令检查工具 SNETCracker超级弱口令检查工具是一款开源的Windows平台的弱口令安全审计工具&#xff0c;支持批量多线程检查&#xff0c;可快速发现弱密码、弱口令账号&#xff0c;密码支持和用户名结合进行检查&am…

第九次作业

1. SSL工作过程是什么&#xff1f; 当客户端向一个 https 网站发起请求时&#xff0c;服务器会将 SSL 证书发送给客户端进行校验&#xff0c;SSL 证书中包含一个公钥。校验成功后&#xff0c;客户端会生成一个随机串&#xff0c;并使用受访网站的 SSL 证书公钥进行加密&#xf…