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

Nature重磅:量子生物学重大突破

来源&#xff1a;一直奇怪2026 年 3 月 18 日&#xff0c;斯坦福大学的研究人员在国际顶尖学术期刊 Nature 上发表了题为&#xff1a;Magnetic resonance control of spin-correlated radical pair dynamics in vivo 的研究论文。该研究首次在活体多细胞动物中利用磁共振技术精…...

智能体设计模式详解 B# 附录G:编程代理

【全景】基于双向协同的能力融合设计 Agent设计模式 V1:基于双向协同的能力融合设计 39种设计模式分层清单 A#0 智能体设计模式全景(上):大模型如何“思考”?(认知视角导论) Agent Design Pattern Catalogue: A Collection of Architectural Patterns for Foundation Mo…...

Hunyuan-MT-7B多场景实践:像素语言传送门在独立游戏开发、字幕生成、文档本地化中的三重应用

Hunyuan-MT-7B多场景实践&#xff1a;像素语言传送门在独立游戏开发、字幕生成、文档本地化中的三重应用 1. 像素语言传送门&#xff1a;当翻译遇见16-bit冒险 在独立游戏开发者的工作台上&#xff0c;一款名为"像素语言传送门"的工具正在改变传统翻译体验。这款基…...

OpenClaw自动化写作流:Phi-3-mini-128k-instruct生成技术文章+校对手册

OpenClaw自动化写作流&#xff1a;Phi-3-mini-128k-instruct生成技术文章校对手册 1. 为什么需要自动化写作流 上周我连续写了三篇技术文章后&#xff0c;突然意识到一个严重问题——每次从资料收集到最终排版&#xff0c;至少要消耗4小时。其中真正用于核心内容创作的时间不…...

清华大学重磅突破:让AI汽车真正听懂你说话,想去哪就去哪!

这项由清华大学计算机科学与技术系和GigaAI公司联合开展的研究于2026年3月26日发表在计算机视觉顶级会议论文中&#xff0c;论文编号为arXiv:2603.25741v1。有兴趣深入了解技术细节的读者可以通过该编号查询完整论文内容。汽车能像人类司机一样理解复杂的语言指令&#xff0c;并…...

SpringBoot项目中如何用拦截器优雅解决越权漏洞?附完整代码示例

SpringBoot拦截器实战&#xff1a;三层防御体系解决越权漏洞 在电商系统开发中&#xff0c;我们团队曾遭遇过一次严重的越权事故——某用户通过修改URL参数&#xff0c;成功访问到其他用户的订单详情页面。这次事件让我们意识到&#xff0c;权限控制绝非简单的登录验证就能解决…...

Wan2.1视频生成创意玩法:把你的想法变成动态视觉故事

Wan2.1视频生成创意玩法&#xff1a;把你的想法变成动态视觉故事 1. 从文字到视频的魔法 你有没有过这样的经历&#xff1f;脑海中浮现出一个绝妙的创意场景&#xff0c;却苦于没有专业的视频制作技能将它呈现出来。或许是一个科幻故事的开场&#xff0c;一个产品演示的构想&…...

实战分享:如何用星图平台零代码私有化Qwen3-VL:30B,并接入飞书实现智能对话

实战分享&#xff1a;如何用星图平台零代码私有化Qwen3-VL:30B&#xff0c;并接入飞书实现智能对话 1. 项目概述与价值 在当今企业智能化转型的浪潮中&#xff0c;如何快速部署私有化大模型并实现业务场景落地&#xff0c;成为许多技术团队面临的挑战。本文将详细介绍如何通过…...

从新手小白到资深开发者:GISBox与QGIS如何适配你的成长路径?

随着地理信息技术的加速演进&#xff0c;工具选型已成为提升空间数据处理效率的关键环节。本文立足于产品定位、功能体系与目标用户三大核心维度&#xff0c;系统梳理GISBox与QGIS的差异化特征&#xff0c;旨在为教育、科研、企业及个人开发者提供清晰、务实的工具决策依据。 …...

intv_ai_mk11惊艳输出集:RAG技术通俗解释、电商详情页开头、朋友圈爆款文案

intv_ai_mk11惊艳输出集&#xff1a;RAG技术通俗解释、电商详情页开头、朋友圈爆款文案 1. 什么是intv_ai_mk11 AI对话机器人 intv_ai_mk11是一款基于7B参数Llama架构的AI对话助手&#xff0c;运行在GPU服务器上。它能够理解自然语言并生成高质量的文本回复&#xff0c;适用于…...