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

剑指offer题解合集——Week1day5

剑指offerWeek1

周五:重建二叉树

题目链接:重建二叉树

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。注意:二叉树中每个节点的值都互不相同;
输入的前序遍历和中序遍历一定合法;
数据范围
树中节点数量范围 [0,100]
。样例
给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:3/ \9  20/  \15   7

AC代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:unordered_map<int, int> map;TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for (int i = 0; i < inorder.size(); i ++ ) map[inorder[i]] = i;return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);}TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){if (pl > pr) return nullptr;auto node = new TreeNode(preorder[pl]);int k = map[node->val];node->left = dfs(preorder, inorder, pl + 1, pl + k - il, il, k - 1);node->right = dfs(preorder, inorder, pl + k - il + 1, pr, k + 1, ir);return node;}
};

思路:

整体思路

要时刻牢记前序遍历、中序遍历的特点
前序:第一个遍历的一定是根节点
中序遍历:在根节点的左边一定是左子树,右边则是右子树那么两个性质结合,可以从前序遍历中找到根节点
然后再从中序遍历中,根据根节点划分左右子树
在左右子树中递归以上步骤,则可以重建二叉树本题还有一个难点:
当知道根节点以后,如何划分左右子树
别说什么:哎呀中序遍历知道根节点,左边的不就是左子树吗
注意,我这里指的是:在前序遍历的数集中划分左右子树
这里是利用左右子树区间长度相等得出区间边界

代码思路

  • 利用map构造出中序遍历的值能索引到值对应的下标(为了更好的找到根节点)
  • 递归,递归的条件是:前序遍历集存在
    • 构造根节点
    • 找到根节点的下标值
    • 在左子树中递归
      • 前序遍历区间:第一个节点是pl,也是根节点,因此左子树从pl + 1开始,左子树的右端点待定
      • 中序遍历的区间:左端点为il,右端点为根节点的索引值 - 1
    • 在右子树中递归
      • 右子树
        • 前序遍历区间:左端点待定,右端点显然是pr
        • 中序遍历的区间:左端点为根节点的索引值 + 1,右端点ir
  • 返回根节点

以上有两个待定的端点,也是难点

这里需要利用性质左右子树区间长度相等得出区间边界

记根节点下标为k

由于中序遍历中,左子树区间为[il, k - 1]

前序遍历[pl + 1, 待定]

记前序遍历区间的右端点为x

则有

x - pl - 1 + 1= k - 1 - il + 1

则可以解出x = k - il + pl

则前序遍历中,右子树的左端点显然为这个x + 1

部分模拟

前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]

  • 前序遍历第一个节点为根节点,显然为3
  • 从中序遍历中得到3,因此9是左子树,15, 20, 7是右子树
  • 左子树已经确定
    • 右子树中继续递归即可,例如,右子树的根为20(前序遍历中得出)

相关文章:

剑指offer题解合集——Week1day5

剑指offerWeek1 周五&#xff1a;重建二叉树 题目链接&#xff1a;重建二叉树 输入一棵二叉树前序遍历和中序遍历的结果&#xff0c;请重建该二叉树。注意:二叉树中每个节点的值都互不相同&#xff1b; 输入的前序遍历和中序遍历一定合法&#xff1b; 数据范围 树中节点数量…...

Redis设计与实现之数据库

目录 一、数据库 1、数据库的结构 2、 数据库的切换 3、 数据库键空间 4、键空间的操作 添加新键 删除键 更新键 取值 其他操作 5、 键的过期时间 6、过期时间的保存 7、设置生存时间 8、过期键的判定 9、 过期键的清除 定时删除 惰性删除 定期删除 10、过期…...

如何在Eclipse中安装WindowBuilder插件,详解过程

第一步&#xff1a;找到自己安装eclipse的版本&#xff0c;在Help-关于eclipse里面&#xff0c;即Version 第二步&#xff1a;去下面这个网站找到对应的 link&#xff08;Update Site&#xff09;&#xff0c;这一步很重要&#xff0c;不然版本下载错了之后还得删除WindowBuil…...

node.js mongoose schemaTypes

目录 官方文档 简介 SchemaType 示例 配置SchemaType规则 通用规则 特定schemaType规则 String Number Date Map monggose会根据shcemaType将文档值转换成指定的类型 官方文档 Mongoose v8.0.3: SchemaTypes 简介 SchemaTypes是在使用Mongoose时&#xff0c;用于…...

论文解读:On the Integration of Self-Attention and Convolution

自注意力机制与卷积结合&#xff1a;On the Integration of Self-Attention and Convolution(CVPR2022) 引言 1&#xff1a;卷积可以接受比较大的图片的&#xff0c;但自注意力机制如果图片特别大的话&#xff0c;运算规模会特别大&#xff0c;即上图中右边(卷积)会算得比较快…...

【Spring】15 ApplicationContextAware 接口

文章目录 1. 简介2. 作用3. 使用3.1 创建并实现接口3.2 配置 Bean 信息3.3 创建启动类3.4 启动 4. 应用场景总结 Spring 框架提供了许多回调接口&#xff0c;用于在 Bean 的生命周期中执行特定的操作。ApplicationContextAware 接口是其中之一&#xff0c;它允许 Bean 获取对 A…...

Android 版本控制工具--Git

要在Android中使用Git&#xff0c;需要进行以下步骤&#xff1a; 安装Git&#xff1a;首先在你的开发环境中安装Git。在Windows中&#xff0c;你可以从官方网站&#xff08;https://git-scm.com/downloads&#xff09;上下载Git的可执行文件并进行安装。在Mac上&#xff0c;你可…...

Wireshark高级网络安全分析

第一章&#xff1a;Wireshark基础及捕获技巧 1.1 Wireshark基础知识回顾 1.2 高级捕获技巧&#xff1a;过滤器和捕获选项 1.3 Wireshark与其他抓包工具的比较 第二章&#xff1a;网络协议分析 2.1 网络协议分析&#xff1a;TCP、UDP、ICMP等 2.2 高级协议分析&#xff1a;HTTP…...

llvm后端之DAG设计

llvm后端之DAG设计 引言1 核心类设计2 类型系统2.1 MVT::SimpleValueType2.2 MVT2.3 EVT 3 节点类型 引言 llvm后端将中端的IR转为有向无环图&#xff0c;即DAG。如下图&#xff1a; 图中黑色箭头为数据依赖&#xff1b;蓝色线和红色线为控制依赖。蓝色表示指令序列化时两个节…...

反序列化 [SWPUCTF 2021 新生赛]ez_unserialize

打开题目 查看源代码 得到提示&#xff0c;那我们用御剑扫描一下看看 我们知道有个robots.txt&#xff0c;访问一下得到 那我们便访问一下 cl45s.php看看 得到网站源代码 <?phperror_reporting(0); show_source("cl45s.php");class wllm{public $admin;public …...

centos(linux)安装jenkins

官网&#xff1a;https://pkg.jenkins.io/redhat/ 安装官网进行操作&#xff1a; sudo wget -O /etc/yum.repos.d/jenkins.repo https://pkg.jenkins.io/redhat/jenkins.reposudo rpm --import https://pkg.jenkins.io/redhat/jenkins.io-2023.key若出现如下错误&#xff1a; …...

Wireshark统计和可视化

第一章&#xff1a;Wireshark基础及捕获技巧 1.1 Wireshark基础知识回顾 1.2 高级捕获技巧&#xff1a;过滤器和捕获选项 1.3 Wireshark与其他抓包工具的比较 第二章&#xff1a;网络协议分析 2.1 网络协议分析&#xff1a;TCP、UDP、ICMP等 2.2 高级协议分析&#xff1a;HTTP…...

高通平台开发系列讲解(SIM卡篇)SIM软件架构介绍

文章目录 一、SIM软件架构二、MMG SDI Task三、GSTK Task四、Simlock Task沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇文章将介绍SIM的相关组件。 SIM软件架构: SIM软件架构指的是与SIM卡(Subscriber Identity Module,订阅者身份模块)相关的软件系统设计和…...

音频筑基:瞬态、基音、偏噪信号类型分析

音频筑基&#xff1a;瞬态、基音、偏噪信号类型分析 是什么深入理解从编码角度看&#xff0c;基音信号编码通常会有啥问题&#xff1f;在频域感知编码过程中&#xff0c;瞬态信号会有啥问题&#xff1f;如何解决&#xff1f;瞬态信号场景下&#xff0c;5/10ms帧长编码有啥区别&…...

HarmonyOS ArkTS 中DatePicker先择时间 路由跳转并传值到其它页

效果 代码 代码里有TextTimerController 这一种例用方法较怪&#xff0c;Text ,Button Datepicker 的使用。 import router from ohos.router’则是引入路由模块。 import router from ohos.router Entry Component struct TextnewClock {textTimerController: TextTimerContr…...

Axure RP 8 for Mac/win中文版:打造完美交互式原型设计体验

Axure RP 8&#xff0c;一款引领潮流的交互式原型设计工具&#xff0c;为设计师提供了无限的可能性&#xff0c;让他们能够创造出逼真的原型&#xff0c;从而更好地展示和测试他们的设计。 Axure RP 8拥有丰富的功能和工具&#xff0c;让设计师可以轻松地创建出复杂的交互式原…...

迪文屏开发保姆级教程——页面键盘

迪文屏页面键盘保姆级教程。 本篇文章主要介绍了在DGBUS平台上使用页面键盘的步骤。 迪文屏官方开发指南PDF&#xff1a;&#xff08;不方便下载的私聊我发给你&#xff09; https://download.csdn.net/download/qq_21370051/88647174?spm1001.2014.3001.5503https://downloa…...

Unity的UI界面——Text/Image

编辑UI界面时&#xff0c;要先切换到2d界面 &#xff08;3d项目的话&#xff09; 1.Text控件 Text控件的相关属性&#xff1a; Character:&#xff08;字符&#xff09; Font&#xff1a;字体 Font Style&#xff1a;字体样式 Font Size&#xff1a;字体大小 Line Spac…...

sklearn和tensorflow的理解

人工智能的实现是基于机器学习&#xff0c;机器学习的一个方法是神经网络&#xff0c;以及各种机器学习算法库。 有监督学习&#xff1a;一般数据构成是【特征值目标值】 无监督学习&#xff1a;一般数据构成是【特征值】 Scikit-learn(sklearn)的定位是通用机器学习库&…...

css中BFC

css BFC BFC具有以下特性创建BFC的方式有多种BFC的应用场景和作用 扩展&#xff1a; CSS动画 transition: 过渡动画animation / keyframestransform都有哪些属性 举例 css BFC BFC&#xff0c;即块级格式化上下文&#xff08;Block Formatting Context&#xff09;&#xf…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

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

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

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

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 __…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...