剑指offer打卡 JZ7 重建二叉树

在牛客网刷的,还是跟leetcode一样非acm模式,由于急着暑期实习题量不固定,八股算法轮刷

打卡内容偏个人笔记,本人水平一般(代码随想录稀里糊涂刷了一遍),从小白开始分析(甚至会分析语法),尽量一题多解深入探究(一般ac后看看前三个题解发散下思维),希望能对你有帮助

JZ7 重建二叉树

描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。 

提示: 

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点,系统会自动输出整颗树做答案对比

数据范围:n≤2000,节点的值 −10000≤val≤10000

要求:空间复杂度 O(n),时间复杂度 O(n)

分析

思路数据结构都学过,前序找根节点,中序分割子树

代码刷过再写还是没过,主要不知道写递归还是循环,并且根节点的处理感觉很特殊

于是火速看了算法笔记的二叉树构造部分,记录在我主页算法笔记专栏

上上行提到的问题,还是应该写递归,可以看到同颜色的块是等长的且一个是前序一个是中序,递归参数设置为数组、起始位置和终止位置即可

于是采用前序遍历,做的事是找到inOrder中根节点位置用于后续区间分割

由于有返回值,需要修改代码模板,尽管是前序遍历,在递归函数最后要return root

代码如下:

public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
    TreeNode root = build(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);
    return root;
}

TreeNode build(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
    if (preStart > preEnd) return null;
    
    // Find the index of root node in inorder traversal
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (in[i] == pre[preStart]) {
            index = i;
            break;
        }
    }
    
    int leftSize = index - inStart;
    TreeNode root = new TreeNode(pre[preStart]);
    root.left = build(pre, preStart + 1, preStart + leftSize, in, inStart, index - 1);
    root.right = build(pre, preStart + leftSize + 1, preEnd, in, index + 1, inEnd);
    return root;
}

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

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

相关文章

VSCode好用插件

由于现在还是使用vue2&#xff0c;所以本文只记录vue2开发中好用的插件。 美化类插件不介绍了&#xff0c;那些貌似对生产力起不到什么大的帮助&#xff0c;纯粹的“唯心主义”罢了&#xff0c;但是如果你有兴趣的话可以查看上一篇博客&#xff1a;VSCode美化 1. vuter 简介&…

LabelConvert: 目标检测和图像分割数据集格式转换工具

LabelConvert LabelConvert是一个目标检测和图像分割的数据集格式转换工具&#xff0c;支持labelme、labelImg与YOLO、VOC和COCO 数据集格式之间的相互转换。 支持的转换格式 安装 pip install label_convert具体使用方法 由于文章篇幅所限&#xff0c;请移步LabelConvert官…

左值与右值,以及c++11的相关特性。

目录 左值 右值 左值引用总结&#xff1a; 右值引用总结&#xff1a; 右值引用使用场景和意义&#xff1a; 1、左值引用的使用场景&#xff1a; 编译器优化1&#xff1a; 2、移动构造与移动赋值&#xff1a; 3、右值引用的使用场景&#xff1a; 编译器优化2&#xff1a…

MATLAB科研绘图与学术图表绘制从入门到精通

&#x1f482; 个人网站:【 摸鱼游戏】【神级代码资源网站】【工具大全】&#x1f91f; 一站式轻松构建小程序、Web网站、移动应用&#xff1a;&#x1f449;注册地址&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交…

软件资源分享六:EPLAN Electric P8 2024 | Eplan 2024 中文版软件介绍+保姆级安装教程

原文链接&#xff1a;安装激活教程 EPLAN Electric P8 2024 | Eplan 2024 中文版软件介绍安装教程 EPLAN 2024是一款电气设计软件&#xff0c;它可以用于自动化系统的设计、文档编制和维护。EPLAN可以对电气设计的各个方面进行完整的支持&#xff0c;包括电气控制系统、机械设…

新手学python还是c?

考虑到个人情况和职业规划是非常重要的。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我在后台发给你。 Python作为初学者入门语言…

基于单片机温湿度PM2.5报警设置系统

**单片机设计介绍&#xff0c;基于单片机温湿度PM2.5报警设置系统 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机温湿度PM2.5报警设置系统概要主要涵盖了系统的整体设计思路、硬件组成、软件实现以及报警功能等关键方…

HCIP综合实验1

一.实验拓扑 二.实验要求 1、R5为ISP&#xff0c;只能进行IP地址配置&#xff0c;其所有地址均配为公有Ip地址; 2、 R1和R5间使用PPP的PAP认证&#xff0c;R5为主认证方&#xff1b; R2与R5之间使用PPP的CHAP认证&#xff0c;R5为主认证方; R3与R5之间使用HDLC封装; 3、R2、R3…

高密度集成可伸缩无机薄膜晶体管

引言 与有机晶体管相比&#xff0c;无机半导体晶体管具有优越的性能和可靠性。然而&#xff0c;由于其脆性&#xff0c;不利于制造可拉伸的电子产品。由于这一缺点&#xff0c;它们大多被放置在不可拉伸的部件上&#xff0c;以避免机械应变&#xff0c;加重连接这些刚性部件的…

Java中的可变字符串

Java中的可变字符串 一、什么是可变字符串二、可变字符串的使用场景以及使用步骤1.新建一个可变字符串2.可变字符串的一系列方法 一、什么是可变字符串 可变字符串是Java.lang包下的 在我们学习到JDBC的时候需要将原有的sql语句根据不同的差异添加一段新的关键字或者单词&…

【C语言】函数(涉及生命周期与作用域)

文章目录 函数&#xff08;function&#xff09;**函数的概念****函数的作用**在本阶段一般会涉及到两类函数:库函数和自定义函数自定义函数**函数的语法形式** **形参和实参****实参和形参的关系** 函数返回值**函数返回值类型说明****return 语句** 数组做函数参数**函数嵌套…

C语言:二叉树的构建

目录 一、二叉树的存储 1.1 顺序存储 1.2 链式存储 二、二叉树的顺序结构及实现 2.1堆的概念及结构 2.2堆的构建 2.3堆的插入 2.4堆顶的删除 2.5堆的完整代码 三、二叉树的链式结构及实现 3.1链式二叉树的构建 3.2链式二叉树的遍历 3.2.1前序遍历 …

【笔记】即时通讯设计

记录一下最近对im功能的设计 写扩散 1&#xff09;遍历群聊的成员并发送消息&#xff1b;2&#xff09;群聊所有人都存一份&#xff1b;3&#xff09;查询每个成员的在线状态&#xff1b;4&#xff09;在线的实时推送。 读扩散 1&#xff09;遍历群聊的成员并发送消息&#x…

【Go】二十、反射

文章目录 1、反射2、对基本数据类型反射3、对结构体进行反射4、获取变量的类别5、通过反射修改基本类型变量的值6、通过反射操作结构体的属性和方法 1、反射 //核心包 import ("reflect")通过反射&#xff1a; 可以在运行时动态获取变量的类型、获取结构体的信息&a…

云容器引擎CCE弹性伸缩

CCE弹性伸缩介绍 CCE的弹性伸缩能力分为如下两个维度&#xff1a; 工作负载弹性伸缩&#xff1a;即调度层弹性&#xff0c;主要是负责修改负载的调度容量变化。例如&#xff0c;HPA是典型的调度层弹性组件&#xff0c;通过HPA可以调整应用的副本数&#xff0c;调整的副本数会…

【数字图像处理】颜色空间的转换

颜色空间的转换 CMY 空间 CMY 颜色空间正好与 RGB 颜色空间互补&#xff0c; 即用白色减去 RGB 颜色空间中的某一颜色值就等于这种颜色在 CMY 颜色空间中的值。 { C 1 − R M 1 − G Y 1 − B \begin{cases}C1-R\\M1-G\\Y1-B\end{cases} ⎩ ⎨ ⎧​C1−RM1−GY1−B​ HSV 空…

非关系型数据库(缓存数据库)redis的基础认知与安装

目录 一.关系型数据库和非关系型数据库 关系型数据库 非关系型数据库 关系数据库与非关系型数据库的区别 ①非关系数据 关系型数据库 非关系型数据库产生背景 数据存储流向 非关系型数据库 关系数据库 二.redis的简介 1.概念 2.Redis 具有以下几个优点: 3.Redi…

数据结构二叉树顺序存储——堆

堆 1.堆的概念2.堆的实现 &#xff08;建小堆为例&#xff09;2.1 初始化和销毁2.2 判空2.3 获得堆顶元素和堆的大小2.4 插入2.5 删除 3.堆的构建&#xff08;建小堆为例&#xff09; 1.堆的概念 将若干数据或元素按照完全二叉树的存储方式顺序存储到一个一维数组中&#xff0…

LiDAR和Camera融合的BEV感知算法-BEVFusion

0. 简述 本次给大家讲解一篇非常经典的融合工作叫 BEVFusion&#xff0c;我们依旧从算法动机&开创性思路、主体结构、损失函数以及性能对比四个方面展开 BEVFusion 有两篇文章&#xff0c;本次主要讲解的是阿里和北大的&#xff1a;BEVFusion: A Simple and Robust LiDAR-…

Node | Node.js 版本升级

目录 Step1&#xff1a;下载 Step2&#xff1a;安装 Step3&#xff1a;换源 发现其他博客说的 n 模块不太行&#xff0c;所以老老实实地手动安装 Step1&#xff1a;下载 Node 中文官网&#xff1a;https://nodejs.cn/download 点击后&#xff0c;将会下载得到一个 .msi 文件…