leetcode106从中序与后序遍历序列构造二叉树

目录

  • 1.解题关键
  • 2.思路
  • 3.变量名缩写与英文单词对应关系
  • 4.算法思路图解
  • 5.代码

本文针对原链接题解的比较晦涩的地方重新进行说明解释
原题解链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solutions/50561/tu-jie-gou-zao-er-cha-shu-wei-wan-dai-xu-by-user72

1.解题关键

后序遍历序列的最后一个元素一定是root节点,中序遍历序列里面,root左边的是左子树,root节点右边的是右子树,接着可以递归处理。
依次把数组分为

2.思路

先使用哈希表记录整个中序序列的数组元素与下标的关系,目的是为了后续直接获取后序遍历序列vector最后一个元素之后直接得到中序里面的root节点的下标,加快算法速度!

3.变量名缩写与英文单词对应关系

变量名缩写变量名单词
isinorder_start(中序遍历数组-起始下标)
ieinorder_end(中序遍历数组-末尾下标)
psposter_start(后序遍历数组-起始下标)
peposter_end(后序遍历数组-末尾下标)
riroot_index(根节点的下标)

4.算法思路图解

在这里插入图片描述

在这里插入图片描述

5.代码

class Solution {
public:
    unordered_map<int,int> map;
    vector<int>* post;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {        
        for(int i=0;i<inorder.size();++i){
            map[inorder[i]]=i;
        }
        post=&postorder;
        TreeNode* root=dfs(0,inorder.size()-1,0,post->size()-1);
        return root;
    }
    TreeNode* dfs(int is,int ie,int ps,int pe){
        if(ie<is||pe<ps){
            return nullptr;
        }
        int root = (*post)[pe];
        int ri=map[root];
        TreeNode* node=new TreeNode(root);
        node->left=dfs(is,ri-1,ps,ri-is-1+ps);
        node->right=dfs(ri+1,ie,ri-is+ps,pe-1);
        return node;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

3D Tiles语义分割流水线

Dylan Chua 和 Anne Lee 开发了一个处理管线&#xff0c;用于对 3D Tiles 中包含的 GL 传输格式 (glTF) 模型进行语义分割。 该管道读取并遍历 3D Tileset&#xff0c;以输出包含元数据的经过转换的划分对象集。 该项目为 3D 语义分割器提供了最小可行产品&#xff0c;作为各种…

STM32CubeIDE基础学习-BEEP蜂鸣器实验

STM32CubeIDE基础学习-BEEP蜂鸣器实验 文章目录 STM32CubeIDE基础学习-BEEP蜂鸣器实验前言第1章 硬件介绍第2章 工程配置2.1 工程外设配置部分2.2 生成工程代码部分 第3章 代码编写第4章 实验现象总结 前言 前面学习了LED闪烁实验&#xff0c;现在来学习一下蜂鸣器发声实验&am…

JVM工作原理与实战(四十四):JVM常见面试题目

专栏导航 JVM工作原理与实战 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、JVM常见面试题目 1.有哪些常用的垃圾回收器&#xff1f; 2.什么是内存泄漏&#xff0c;如何解决内存泄漏问题&#xff1f; 3.请列举并简要描述一些常用的JVM工具及其主要功能。 …

用python写网络爬虫:3.urllib库进一步的使用方法

文章目录 异常处理URLErrorHTTPError设置超时时间 链接的解析、构造、合并urlparse方法urlsplit方法urljoin方法urlencode方法parse_qs方法quote方法 Robots 协议Robots 协议的结构解析协议 参考书籍 在上一篇文章&#xff1a;用python写网络爬虫&#xff1a;2.urllib库的基本用…

Nginx底层基础数据结构

基础数据结构 ngx_int_t 32位操作系统4字节,64位操作系统8字节 解决跨平台以及,普通int类型在x86和x64操作系统上面是4字节,在类型转换时造成内存浪费(如在x64下面转换long类型) typedef intptr_t ngx_int_t;#ifdef _WIN64 typedef __int64 intptr_t; #else typedef _…

Canal实现mysql与缓存同步

什么是Canal Canal是阿里巴巴旗下的一款开源项目, 基于java开发. Canal是基于mysql的主从同步来实现的. github地址: https://github.com/alibaba/canal Canal把自己伪装成MySQL的一个slave节点, 从而监听master的binary log变化. 再把得到的变化信息通知给Canal的客户端, 进而…

vue3 element plus 上传下载

文章目录 上传下载 上传 /* html */ <el-upload v-model"fileId" class"avatar-uploader" ref"exampleUploadRef" :file-list"fileList" :show-file-list"false" action"/ys-three-year/ThreeReport/uploadFile&q…

Python从0到100(五):Python分支结构和循环结构

一、分支结构&#xff1a; Python中的分支结构和循环结构是编写程序时常用的控制结构。在Python中&#xff0c;分支结构通过if、elif和else关键字来实现条件判断。在使用if语句时&#xff0c;程序会根据条件表达式的真假执行相应的代码块。 if condition1:# 如果条件1为真&am…

YOLOv5改进 | 图像去雾 | 利用图像去雾网络UnfogNet辅助YOLOv5进行图像去雾检测(全网独家首发)

一、本文介绍 本文给大家带来的改进机制是利用UnfogNet超轻量化图像去雾网络,我将该网络结合YOLOv5针对图像进行去雾检测(也适用于一些模糊场景),我将该网络结构和YOLOv5的网络进行结合同时该网络的结构的参数量非常的小,我们将其添加到模型里增加的计算量和参数量基本可…

每天一点正压采样器小知识

只要你奔跑&#xff0c;这个世界就会跟着你奔跑&#xff0c; 只要你停驻&#xff0c;这个世界就会舍弃你独自奔跑&#xff0c; 唯有你确定一个方向&#xff0c;使劲的跑起来&#xff0c; 这个世界会为你而让路。 每天一点正压采样器小知识 该采样器活赛与气筒采用全金属密封&am…

操作系统知识-存储管理+文件管理管理-嵌入式系统设计师备考笔记

0、前言 本专栏为个人备考软考嵌入式系统设计师的复习笔记&#xff0c;未经本人许可&#xff0c;请勿转载&#xff0c;如发现本笔记内容的错误还望各位不吝赐教&#xff08;笔记内容可能有误怕产生错误引导&#xff09;。 本章的主要内容见下图&#xff1a; 1、存储管理&#…

[c++]内存管理

1. C/C内存分布 我们先来看下面的一段代码和相关问题 int globalVar 1; static int staticGlobalVar 1; void Test() { static int staticVar 1; int localVar 1; int num1[10] { 1, 2, 3, 4 }; char char2[] "abcd"; const char* pChar3 "abcd"; …

Redis 八种常用数据类型详解

夯实基础&#xff0c;这篇文章带着大家回顾一下 Redis 中的 8 种常用数据类型&#xff1a; 5 种基础数据类型&#xff1a;String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Set&#xff08;集合&#xff09;、Hash&#xff08;散列&#xff09;、Zse…

想进阿里?先搞懂Spring Bean的循环依赖!

如有疑问或者更多的技术分享,欢迎关注我的微信公众号“知其然亦知其所以然”! 嗨,小伙伴们!我是小米,你们的技术分享小助手!今天我们要聊的话题可是技术圈内颇为热门的“阿里巴巴面试题:Spring的循环依赖”哦!相信很多小伙伴都会在技术面试中遇到类似的问题,没错,循…

QT网络编程之获取本机网络信息

一.概述 查询一个主机的MAC地址或者IP地址是网络应用中常用到的功能&#xff0c;Qt提供了QHostInfo和QNetworkInterface 类可以用于此类信息的查询 1.QHostInfo 类&#xff08;显示和查找本地的信息&#xff09; 2.QNetworkInterface 类&#xff08;获得应用程序上所在主机的…

8.JavaWebHTML标签与CSS页面美化和布局控制

目录 导语&#xff1a; 一、HTML表单标签 二、CSS页面美化和布局控制 结语&#xff1a; 导语&#xff1a; 在Web开发中&#xff0c;HTML和CSS是两个不可或缺的技术。HTML&#xff08;HyperText Markup Language&#xff09;用于构建网页的结构&#xff0c;而CSS&#xff08…

【送书福利第五期】:ARM汇编与逆向工程

文章目录 &#x1f4d1;前言一、ARM汇编与逆向工程1.1 书封面1.2 内容概括1.3 目录 二、作者简介三、译者介绍&#x1f324;️、粉丝福利 &#x1f4d1;前言 与传统的CISC&#xff08;Complex Instruction Set Computer&#xff0c;复杂指令集计算机&#xff09;架构相比&#…

RabbitMQ的幂等性、优先级队列和惰性队列

文章目录 前言一、幂等性1、概念2、消息重复消费3、解决思路4、消费端的幂等性保障5、唯一 ID指纹码机制6、Redis 原子性 二、优先级队列1、使用场景2、如何添加3、实战 三、惰性队列1、使用场景2、两种模式3、内存开销对比 总结 前言 一、幂等性 1、概念 2、消息重复消费 3、…

day12-SpringBootWeb 登录认证

一、登录功能 Slf4j RestController public class LoginController {Autowiredprivate EmpService empService;PostMapping("/login")public Result login(RequestBody Emp emp){log.info("员工登录: {}", emp);Emp e empService.login(emp);//登录失败, …

2024考研国家线公布,各科分数线有哪些变化?考研国家线哪些涨了,哪些跌了?可视化分析告诉你

结论在文章结尾 2024考研国家线 一、近五年国家线趋势图-学术硕士 文学 管理学 工学照顾专业 体育学 交叉学科 军事学 历史学 理学 享受少数名族照顾政策的考生 中医类照顾专业 教育类 艺术类 医学 工学 哲学 法学 农学 经济学 二、近五年国家线趋势图-专业硕士 中医 应用心理 …