LeetCode105.从前序与中序遍历构造二叉树

题目要求

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

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解题思路

一般而言,知道一个二叉树的前序遍历和中序遍历就可以确定为唯一二叉树,前提是没有重复的子元素在里面。

在前序遍历中,我们知道一般是通过根左右的顺序进行遍历,所以我们可以在前序遍历中找到根节点,和当前根节点的左子树右子树的根节点。

而在中序遍历中,根节点的左边是所有左子树的节点,根节点的右边是所有右子树的节点,依此我们可以推断出左右子树的长度。

根据根节点,左右子树的长度作为条件,可以使用回溯的方式进行二叉树的构建。

算法流程

递推参数

根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right 。

终止条件

当 left > right ,代表已经越过叶节点,此时返回 null 。

递推工作

1. 建立根节点 node : 节点值为 preorder[root] 。
2. 划分左右子树: 查找根节点在中序遍历 inorder 中的索引 i 。、
3. 构建左右子树: 开启左右子树递归。

代码解析

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> map;int[] preorder;int[] inorder;public TreeNode buildTree(int[] preorder, int[] inorder) {//首先建立中序遍历的哈希表,方便根据根节点的值找到根节点的位置HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}this.map = map;this.preorder = preorder;this.inorder = inorder;return recursion(0,0,inorder.length-1);}public TreeNode recursion(int root, int left, int right) {//终止条件if(left > right){return null;}//构建当前根节点TreeNode rootNode = new TreeNode(preorder[root]);//当前根节点在中序遍历中的索引位置int rootInOrderindex = map.get(preorder[root]);//开始递归构建左子树//左子树的根节点:当前根节点在前序遍历的索引+1,因为 根左右//左子树的左节点:在中序遍历中,第一个节点必定在左子树中,所以左子树的左节点必定是left = 0//左子树的右节点:中序遍历中,右节点必定是当前根节点在中序遍历中的索引位置-1rootNode.left = recursion(root+1,left,rootInOrderindex-1);//开始递归构建右子树//右子树的根节点:在前序遍历中,当前根节点加上左子树的长度之后,再加一个节点就是有字数的根节点//右子树的左节点:在中序遍历中,右子树的左节点一般是根节点在中序遍历中的索引+1//右子树的右节点:中序遍历中,右子树的右节点是中序遍历的最后一个节点rootNode.right = recursion(root + rootInOrderindex - left +1,rootInOrderindex+1,right);return rootNode;}
}

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

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

相关文章

【问卷调研】HarmonyOS SDK开发者社区用户需求有奖调研

问卷请点击&#xff1a;HarmonyOS SDK开发者社区用户需求有奖调研

IOT物联网低代码可视化大屏解决方案汇总

目录 参考来源云服务商阿里云物联网平台产品主页产品文档 开源项目DGIOT | 轻量级工业物联网开源平台项目特点项目地址开源许可 IoTGateway | 基于.NET6的跨平台工业物联网网关项目特点项目地址开源许可 IoTSharp | 基于.Net Core开源的物联网基础平台项目特点项目地址开源许可…

如何在Mac上切换到JDK 17开发环境

在本文中&#xff0c;我将为您介绍如何在Mac上切换到JDK 17&#xff0c;包括下载和安装JDK 17、设置环境变量、在IntelliJ IDEA中配置项目、修改Maven编译配置&#xff0c;并最终使用mvn clean install重新编译项目。通过这个流程&#xff0c;您可以顺利地将开发环境升级到JDK …

玩转ChatGPT:文献阅读 v2.0

一、写在前面 好久不更新咯。 因为最近ChatGPT更新了不少功能&#xff08;水一篇刷存在感&#xff09;&#xff1a; 上线ChatGPT-4o模型&#xff0c;说推理能力还不错&#xff1b;上线联网功能&#xff0c;类似Kimi那种。 所以呢&#xff0c;用它来读文献就挺舒服的了。例如…

自动驾驶系列—从数据采集到存储:解密自动驾驶传感器数据采集盒子的关键技术

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

HarmonyOS本地存储-Preferences(用户首选项)的使用

一&#xff0c;用户首选项简述 ohos.data.preferences (用户首选项) 用户首选项为应用提供Key-Value键值型的数据处理能力&#xff0c;支持应用持久化轻量级数据&#xff0c;并对其修改和查询。 数据存储形式为键值对&#xff0c;键的类型为字符串型&#xff0c;值的存储数据…

SpringCloud 微服务消息队列灰度方案 (RocketMQ 4.x)

目录 背景遇到的问题 RocketMQ 基础基础消息模型扩展后的消息模型部署模型相关概念点 方案对比影子Topic的方案Tag的方案UserProperty的方案影子Group的方案灰度分区的方案方案对比 灰度分区方案设计适配只有部分灰度的情况所做的功能扩展消费者&#xff08;无灰度&#xff09;…

「QT」文件类 之 QDataStream 数据流类

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「QT」QT5程序设计&#x1f4da;全部专栏「Win」Windows程序设计「IDE」集成开发环境「UG/NX」BlockUI集合「C/C」C/C程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「UG/NX」NX定制…

QT<30> Qt中使鼠标变为转圈忙状态

前言&#xff1a;当我们在写软件时&#xff0c;在等待阻塞耗时操作时可以将鼠标变为忙状态&#xff0c;并在一段时间后恢复状态&#xff0c;可以用到GxtWaitCursor&#xff1a;Qt下基于RAII的鼠标等待光标类。 一、效果演示 二、详细代码 在项目中添加C文件&#xff0c;命名为…

Vue的基础使用

一、为什么要学习Vue 1.前端必备技能 2.岗位多&#xff0c;绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能&#xff08;Vue2Vue3&#xff09; 二、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 构建用户界面 的 渐进式 框架…

数据结构Python版

2.3.3 双链表 双链表和链表一样&#xff0c;只不过每个节点有两个链接——一个指向后一个节点&#xff0c;一个指向前一个节点。此外&#xff0c;除了第一个节点&#xff0c;双链表还需要记录最后一个节点。 每个结点为DLinkNode类对象&#xff0c;包括存储元素的列表data、…

FBX福币交易所恒指收跌1.96% 半导体股继续回调

查查配分析11月14日电 周四,港股三大指数集体下跌。截至收盘,恒生指数跌1.96%,恒生科技指数跌3.08%,恒生中国企业指数跌2.21%。大市成交额1733亿港元。 FBX福币凭借用户友好的界面和对透明度的承诺,迅速在加密货币市场中崭露头角,成为广大用户信赖的平台。 来源:Wind 盘面上,科…

【学习日记】notebook添加JAVA支持

作者是个大学生 这个专栏主要收集课时常用的软件 以及女朋友上课用的软件的教程 新开了gitcode 用于上传安装包 环境说明 windows11 java23.0.1 ijava1.1.2 Anaconda-2024.02 需提前配置好java环境 本篇仅对添加支持进行说明 ijava的GitCode链接NotebookAddsSupportForJava:no…

RabbitMQ 篇-深入了解延迟消息、MQ 可靠性(生产者可靠性、MQ 可靠性、消费者可靠性)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 RabbitMQ 的可靠性 2.0 发送者的可靠性 2.1 生产者重试机制 2.2 生产者确认机制 2.2.1 开启生产者确认机制 2.2.2 定义 ReturnCallback 机制 2.2.3 定义 ConfirmC…

【数据结构】AVL树

引言&#xff1a;在实际情况中&#xff0c;数据不仅仅要存储起来&#xff0c;还要进行对数据进行搜索&#xff0c;为了方便进行高效搜索(在此之前的数据结构的搜索基本都是暴力搜索)二叉搜索树应运而生。但是在极端情况下(我们按照有序的方式进行插入)&#xff0c;二叉搜索树就…

CSS的综合应用例子(网页制作)

这是html的一些最基本内容的代码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <t…

MySQL查询某个数据库中特定表的空间占用大小

如果您也想要查询某个数据库中特定表的空间占用大小&#xff0c;包括数据和索引的大小&#xff0c;那么您可以使用以下SQL查询。这个查询将显示特定表在数据库中的数据大小、索引大小以及总大小。 SELECT table_name AS Table,ROUND(((data_length index_length) / 1024 / 10…

Towards Reasoning in Large Language Models: A Survey

文章目录 题目摘要引言什么是推理?走向大型语言模型中的推理测量大型语言模型中的推理发现与启示反思、讨论和未来方向 为什么要推理?结论题目 大型语言模型中的推理:一项调查 论文地址:https://arxiv.org/abs/2212.10403 项目地址: https://github.com/jeffhj/LM-reason…

进入未来城:第五周游戏指南

欢迎来到 Alpha 第 4 季第五周&#xff01; 走进霓虹闪烁的未来城街道&#xff0c;这是一座科技至上的赛博朋克大都市。鳞次栉比的摩天大楼熠熠生辉&#xff0c;拥挤的街道下则是阴森恐怖的地下世界。在这里&#xff0c;像激光鹰队长这样的超级战士正在巡逻&#xff0c;而 Ago…

斯坦福泡茶机器人DexCap源码解析:涵盖收集数据、处理数据、模型训练三大阶段

前言 因为我司「七月在线」关于dexcap的复现/优化接近尾声了(每月逐步提高复现的效果)&#xff0c;故准备把dexcap的源码也分析下&#xff0c;11月​下旬则分析下iDP3的源码——为队伍「iDP3人形的复现/优化」助力 最开始&#xff0c;dexcap的源码分析属于此文《DexCap——斯…