当前位置: 首页 > news >正文

Leetcode-每日一题【剑指 Offer 07. 重建二叉树】

题目

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]


示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制:

  • 0 <= 节点个数 <= 5000

解题思路

1.题目要求我们利用前序遍历和中序遍历构建出二叉树,我们可以画图来理解一下

举个例子:

根据我们对数据结构中二叉树部分的学习,我们知道前序遍历是(根左右)所以第一个元素一定是这颗二叉树的根。

 

那么中序遍历是(左右根),所以数字 3 左边的是它的左子树部分,右边的是他的右子树部分。 设 3 在数组 inorder中的下标为 i,

前序遍历:左子树部分 [ l1 + 1, l1 + (i - l2) ]     右子树部分 [l2, i - 1]

中序遍历:左子树部分 [l1 + (i - l2) + 1, r1]    右子树部分[i + 1, r2]

 

 我们按照这个思想继续处理 3 的左子树和右子树, 也就是进行递归操作,

3 的左子树中 9 为根节点,那么 5 和 6 为 9 的左右子树,3 的右子树中 20 为根节点,15 和7 为 3 的左右子树。最终生成的数如下图所示

 2.代码部分首先我们判断所给数组是否为空,若为空直接返回 null;然后我们新建一个map 用于存储inorder数组的下标和对应的值,方便我们后序对 root 所对应的数组下标进行查找。

然后我们让root = f( ) 函数。

3.f( ) 函数的作用是利用传入的前序遍历和中序遍历的数组,找到二叉树的 root 节点,并将数组划分为 root 节点的左右子树。结束条件为 r1 < l1 && r2 < l2。处理完成后返回 root 即可。

代码实现

class Solution {Map<Integer,Integer> map = new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder == null || preorder.length <= 0){return null;}for(int i = 0; i < inorder.length; i++){map.put(inorder[i],i);}TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);return root;}public TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){if(r1 < l1 && r2 < l2){return null;}TreeNode root = new TreeNode(preorder[l1]);int i = map.get(preorder[l1]);root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i - 1);root.right = f(preorder,l1 + (i - l2) + 1, r1, inorder, i + 1, r2);return root;}
}

测试结果

 

 

相关文章:

Leetcode-每日一题【剑指 Offer 07. 重建二叉树】

题目 输入某二叉树的前序遍历和中序遍历的结果&#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7]Output: [3,9,20,null,null,15,7] 示例 2: Input: preo…...

Shell编程快速入门

Shell编程快速入门 脚本格式要求 脚本以#!/bin/bash开头脚本需要有可执行权限 脚本的常用执行方式 方式1&#xff1a;输入脚本的绝对路径或相对路径方式2&#xff1a;sh脚本 Shell的变量 Shell变量介绍 Linux Shell中的变量分为系统变量和用户自定义变量 系统变量&#…...

wpf 3d 坐标系和基本三角形复习

wpf 3d 坐标系的描述见此&#xff0c; WPF 3d坐标系和基本三角形_wpf 坐标系_bcbobo21cn的博客-CSDN博客 X轴正向向右&#xff0c;Y轴正向向上&#xff1b;Z轴&#xff0c;正向是从屏幕里边出来&#xff0c;负向是往屏幕里边去&#xff1b;坐标原点是在呈现区域的中心&#x…...

如何安全变更亚马逊收款账户?

有太多的卖家想知道如何安全变更亚马逊收款账户&#xff0c;因为更改了第三方收款账户可能会导致二次视频认证或者增强视频。真的是这样吗&#xff1f; 其实不推荐亚马逊店铺正常运营之后去变更信用卡&#xff0c;收款账户等重要资料的&#xff0c;因为玩黑科技的卖家也真的多…...

大数据面试题:Hadoop中的几个进程和作用

面试题来源&#xff1a; 《大数据面试题 V4.0》 大数据面试题V3.0&#xff0c;523道题&#xff0c;679页&#xff0c;46w字 可回答&#xff1a;1&#xff09;启动Hadoop&#xff0c;都会有什么进程 参考答案&#xff1a; 1&#xff09;NameNode&#xff1a;Master&#xf…...

题解:ABC276D - Divide by 2 or 3

题解&#xff1a;ABC276D - Divide by 2 or 3 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;入门。 思维难度&#xff1a;入门。 调码难度&#xff1a;入门。 综合评价&#xff1a;极简。 算法 数论。 思路 由大脑可知&#x…...

后台管理系统

1.1 项目概述 简易后台管理系统是一个基于Vue3ElemrntPlus的后台管理系统&#xff0c;提供了用户登录、记住密码、数据的增删改查、分页、错误信息提示等功能&#xff0c;旨在协助管理员对特定数据进行管理和操作。 没有后台对接&#xff0c;数据源为假数据。 全部代码已上传G…...

C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

本文目录 00.BBST——平衡二叉搜索树01.AVL树02.AVL的插入2.1单旋——zig 与 zag2.2插入节点后的单旋实例2.3手玩小样例2.4双旋实例2.5小结 03.AVL的删除3.1单旋删除3.2双旋删除3.3小结 04.34重构05.综合评价AVL5.1优点5.2缺点 06.代码注意插入算法删除算法完整代码&#xff1a…...

静态库和动态库

库文件 库文件是计算机上的一类文件&#xff0c;可以简单的把库文件看成一种代码仓库&#xff0c;它提供给使用者一些可以直接拿来用的变量、函数或类。 库是特殊的一种程序&#xff0c;编写库的程序和编写一般的程序区别不大&#xff0c;只是库不能单独运行。库文件有两种&a…...

用于Voronoi图构建的Fortune算法的C++实现

Voronoi图是一种在计算几何中广泛使用的数据结构&#xff0c;它可以用于解决最近邻搜索、路径规划等问题。在这篇文章中&#xff0c;我们将探讨一种用于构建Voronoi图的高效算法——Fortune算法&#xff0c;并提供其C实现。 一、Voronoi图简介 Voronoi图是由一组点在平面上生…...

笔记汇总 | 斯坦福 CS229 机器学习

文章目录 前言课程参考文章推荐阅读 前言 本文为斯坦福大学 CS229 机器学习课程学习笔记 本文主体部分转载自黄海广博士&#xff0c;文末已给出链接&#xff0c;大家有兴趣可以直接访问笔记首页&#xff0c;下载对应课程资料及作业代码 课程官网&#xff1a;CS229: Machine …...

git 版本管理工具 学习笔记

git 学习笔记 目录 一、git是什么 二、创建仓库 三、工作区域和文件状态 四、添加和提交文件 五、回退版本 &#xff08;了解&#xff09; 六、查看差异 七、删除文件 八、.gitignore文件&#xff08;了解&#xff09; 九、github ssh-key配置 十、本地仓库和远程仓库内…...

Bean基本注解开发和Bean依赖注入注解开发

目录 1.Bean基本注解开发 Component Scorelazy PostConstruct和PreDestroy RepositoryServiceController 2.Bean依赖注入注解开发 Value Autowired Qualifier Resource 扩展AutoWired 1.Bean基本注解开发 基本Bean注解&#xff0c;主要是使用注释的方式替代原有xml的…...

使用IIS服务器搭建一个网站

参考文章 使用IIS&#xff08;Internet Information Services&#xff09;服务器搭建一个网站相对来说是比较简单的。以下是基本的步骤&#xff1a; 安装IIS&#xff1a; 首先&#xff0c;确保你的操作系统已经安装了IIS。在大多数Windows版本中&#xff0c;IIS都是可选安装项…...

HCIP 三层交换机

一、实现VLAN间通信 在传统的交换机组网中&#xff0c;默认所有网络都处于同一个广播域&#xff0c;带来了许多问题&#xff0c;VLAN技术的提出&#xff0c;满足了二层组网隔离广播域需求&#xff0c;使得属于不同的VLAN间网络无法通信&#xff0c;但不同VLAN之间又存在着互相…...

利用python 进行数据分析(第三版)第二章小结

利用python 进行数据分析&#xff08;第三版&#xff09;第二章小结 由于是闲暇时间看的&#xff0c;且为读书笔记&#xff0c;所以只会写一些心得和容易混淆的知识&#xff0c;简单知识将不在重复 在变量或者函数后使用?可以查看详细信息。?还有最后一个用途&#xff0c;即…...

【ASP.NET MVC】使用动软(四)(12)

一、筛选器类和Cookie实现路由 需解决的问题&#xff1a; 网站登录往往需要用户名密码验证&#xff0c;为避免重复验证&#xff0c;一般采用Cookie 、Session等技术来保持用户的登录状态&#xff1a; Session是在服务端保存的一个数据结构&#xff0c;用来跟踪用户的状态&…...

【web逆向】全报文加密及其登录流程的分析案例

aHR0cHM6Ly9oZWFsdGguZWxkZXIuY2NiLmNvbS9zaWduX2luLw 涉及加密库jsencrypt 定位加密点 先看加密的请求和响应&#xff1a; 全局搜索加密字段jsondata&#xff0c;这种非特定参数的一般一搜一个准&#xff0c;搜到就是断点。起初下的断点没停住&#xff0c;转而从调用栈单步…...

MyBatis枚举映射类讨论

前言 本篇需要对于MyBatis有一定的认识&#xff0c;而且只是针对于TypeHandler接口来讨论&#xff0c;暂不讨论其他方面的问题 TypeHandler概叙 TypeHandler是MyBatis设计的一个用于参数的接口&#xff0c;你们会不会很好奇MyBatis是如何把整形&#xff0c;时间&#xff0c;字符…...

微信开发之朋友圈自动点赞的技术实现

简要描述&#xff1a; 朋友圈点赞 请求URL&#xff1a; http://域名地址/snsPraise 请求方式&#xff1a; POST 请求头Headers&#xff1a; Content-Type&#xff1a;application/jsonAuthorization&#xff1a;login接口返回 参数&#xff1a; 参数名必选类型说明wId…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

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

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

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...