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

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...