【LeetCode】剑指 Offer 07. 重建二叉树 p62 -- Java Version
题目链接:https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
1. 题目介绍(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
2. 题解
2.1 递归

时间复杂度:O(n),空间复杂度:O(n)
但下列解法仅适用于 “无重复节点值” 的二叉树。
原因在于我们使用了HashMap来存储中序遍历的值和索引,也就默认了它的值是唯一的。
前序遍历性质: 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质: 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
这里的递归用到了分治的思想,通过前序遍历,我们很容易就可以找到根节点,然后我们就可以拿着这个根节点的值去中序遍历中找,此时中序遍历根节点的左边就属于当前根的左子树,右边就属于当前根的右子树,以此类推…
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {// 1. 定义前序遍历索引,用于定位当前前序遍历所在的位置int preorderIndex = 0;// 2. 创建一个哈希表,用于存储中序遍历节点的位置// 后续想要查找元素,就可以将时间复杂度降为O(1)HashMap<Integer,Integer> inorderMap = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {// 3. 循环遍历,依次将inorder元素添加到哈希表中for (int i = 0; i < inorder.length; i++){inorderMap.put(inorder[i],i);}// 8. 最后返回根节点return arrayToTree(preorder,0,preorder.length-1);}public TreeNode arrayToTree(int[] preorder,int start, int end){// 4. 递归的出口,如果左边位置移动到超过右边,表示走完了,返回空if (start > end) return null;// 5. 创建一个TreeNode对象,用来保存当前的根节点TreeNode root = new TreeNode();root.val = preorder[preorderIndex++];// 6. 递归找左子树、递归找右子树root.left = arrayToTree(preorder,start,inorderMap.get(root.val)-1); root.right = arrayToTree(preorder,inorderMap.get(root.val)+1,end);// 7. 当前递归结束,返回当前节点return root;}
}

此外还有很多其它解法,例如通过迭代加辅助栈的方法来求解,具体内容可参考[2] 重建二叉树(力扣官方题解).
3. 可参考
[1] 剑指 Offer 07. 重建二叉树(分治算法,清晰图解)
[2] 重建二叉树(力扣官方题解)
[3] 【LeetCode】No.105. Construct Binary Tree from Preorder and Inorder Traversal – Java Version (重复)
相关文章:
【LeetCode】剑指 Offer 07. 重建二叉树 p62 -- Java Version
题目链接:https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/ 1. 题目介绍(07. 重建二叉树) 输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的…...
ERROR 1114 (HY000): The table ‘tt2‘ is full
insert 操作时提示is full 问题原因 rootlocalhost 11:55:41 [t]>show table status from t like ‘tt2’ \G ; *************************** 1. row *************************** Name: tt2 Engine: MEMORY Version: 10 Row_format: Fixed Rows: 7056 Avg_row_length: 944…...
考了PMP证后工资大概是多少 ?(含pmp资料)
这个岗位的不同还有每个公司的薪资也是不一样的,具体的数字肯定是没有的,但大概的比例还是有的,据PMI调查,在获得PMP证书的人当中,在PMP认证一年后,年薪有所增长的比例为66%,上涨幅度主要集中在…...
基于国产龙芯 CPU 的气井工业网关研究与设计(一)
当前,我国气田的自动化控制程度还未完全普及,并且与世界已普及的气井站的自 动化程度也存在一定的差距。而在天然气资源相对丰富的国家,开采过程中设备研发资 金投入较大,研发周期较长,更新了一代又一代的自动化开采系…...
40/365 javascript 数据类型
1.数据类型 number类型:整数,小数都属于这一类,不具体区分 字符串:hello, "hello" 布尔类型:true,false 逻辑运算符: && || ! 比较运算符: : 类型不一致&#x…...
后勤管理系统—服务台管理功能
数图互通是一家IT类技术型软件科技公司,专业的不动产、工作场所、空间、固定资产、设备家具、设施运维及可持续性管理解决方案软件供应商。 一、后勤管理系统服务台管理功能包含: 1、专业自动化、集中管理的自助服务助理,随时响应服务请求。…...
Spring Boot 是什么,应该如何学习,有哪些优缺点
1、Spring Boot 是什么? Spring Boot是一个基于Spring框架的开源项目,它简化了Spring应用程序的开发过程,提供了一种快速、便捷、可扩展的方式来构建Spring应用程序。 Spring Boot通过自动化配置机制简化了Spring应用程序的配置过程&#x…...
使用yolov5和强化学习训练一个AI智能欢乐斗地主(一)
这里写自定义目录标题项目介绍项目过程介绍训练yolov5目标检测斗地主收集数据集yolov5调参项目介绍 你好! 欢迎阅读我的文章,本章将介绍,如何使用yolov5和强化学习训练一个AI斗地主,本项目将分为三个部分,其中包含&am…...
C++ 浅谈之 AVL 树和红黑树
C 浅谈之 AVL 树和红黑树 HELLO,各位博友好,我是阿呆 🙈🙈🙈 这里是 C 浅谈系列,收录在专栏 C 语言中 😜😜😜 本系列阿呆将记录一些 C 语言重要的语法特性 dz…...
【Kotlin】Kotlin函数那么多,你会几个?
目录标准函数letrunwithapplyalsotakeIftakeUnlessrepeat小结作用域函数的区别作用域函数使用场景简化函数尾递归函数(tailrec)扩展函数高阶函数内联函数(inline)inlinenoinlinecrossinline匿名函数标准函数 Kotlin标准库包含几个…...
饲养员喂养动物-课后程序(JAVA基础案例教程-黑马程序员编著-第四章-课后作业)
【案例4-2】饲养员喂养动物 记得 关注,收藏,评论哦,作者将持续更新。。。。 【案例目标】 案例描述 饲养员在给动物喂食时,给不同的动物喂不同的食物,而且在每次喂食时,动物都会发出欢快的叫声。例如&…...
数据分析:消费者数据分析
数据分析:消费者数据分析 作者:AOAIYI 创作不易,如果觉得文章不错或能帮助到你学习,记得点赞收藏评论一下哦 文章目录数据分析:消费者数据分析一、前言二、数据准备三、数据预处理四、个体消费者分析五、用户消费行为总…...
Transformer论文阅读:ViT算法笔记
标题:An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale 会议:ICLR2021 论文地址:https://openreview.net/forum?idYicbFdNTTy 文章目录Abstract1 Introduction2 Related Work3 Method3.1 Vision Transformer3.2…...
Android基础练习解答【2】
文章目录一 填空题二 判断题三 选择题四 简答题一 填空题 1.除了开启开发者选项之外,还需打开手机上的 usb调试 开关,然后才能在手机上调试App。 2.App开发的两大技术路线包括 _原生开发_和混合开发。 3.App工程的编译…...
k8s 搭建
需求:搭建k8s 为后续自动部署做准备进程:安装至少两个ubuntu18.04系统(一个master 一到多个 node)每个系统上都要装上docker 和 kubernetes安装dockersudo su apt-get update#安装相关插件 apt-get install apt-transport-https c…...
安全运维之mysql基线检查
版本加固 选择稳定版本并及时更新、打补丁。 稳定版本:发行6-12个月以内的偶数版本。 检查方法: 使用sql语句:select version(); 检查结果: 存在问题:当前数据库版本较老需要更新 解决方案:前往http://www.mysql…...
跨境电商卖家敦煌、雅虎、乐天、亚马逊测评自养号的重要性!
作为亚马逊、敦煌、乐天、雅虎等跨境的卖家,这两年以来,面对流量越来越贵的现实,卖家需要更加珍惜每次访问listing页面的流量,把转化做好,把流量尽可能转化为更多的订单。 提升转化率的技巧 提升产品转化率࿰…...
Python 之 Matplotlib xticks 的再次说明、图形样式和子图
文章目录一. 改变 x 轴显示内容 xticks 方法再次说明1. x 轴是数值型数据2. 将 x 轴更改为字符串3. 总结二. 其他元素可视性1. 显示网格:plt.grid()2. plt.gca( ) 对坐标轴的操作三. plt.rcParams 设置画图的分辨率,大小等信息四. 图表的样式参数设置1. …...
3.InfluxDB WEB使用
结合telegraf做指标数据收集 点击 Load Data -> Telegraf 配置界面 influxDB支持在WEB-UI中生成配置文件 然后利用telegraf通过远程URL请求的方式进行获取 点击CREATE CONFIGURATION 创建telegraf配置文件 选择Bucket InfluxDB提供了很多配置好的监控模板供用户选择 可以…...
git冲突合并
一、版本说明 dev:本地仓库中的dev分支 master:本地仓库中的master分支 remotes/origin/master和origin/master:都是远程仓库上的master分支 二、一个解决冲突的常规流程 1、前提条件:不能在master分支上修改任何文件。master分支…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
