当前位置: 首页 > 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…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...