【力扣每日一题】2023.9.4 序列化和反序列化二叉搜索树

目录

题目:

示例:

分析:

代码:


题目:

示例:

分析:

题目给我们一棵搜索二叉树,要我们将这棵二叉树转变为字符串,同时我们需要根据字符串再变回二叉树,具体的方法我们可以自行制定。

这道题让我想起了力扣的另外一道题:

我们可以把二叉树的前序遍历和中序遍历的结果压缩成字符串。

要由字符串变为二叉树的时候,可以通过字符串分割出前序遍历和中序遍历,再通过前序与中序遍历序列构造二叉树。

因此我们今天的重点放在这道105题上。

我们应该如何通过前序遍历的结果和中序遍历的结果来构造二叉树?

我们先看看两者的结果分别有什么特点。

我们知道,前序遍历和中序遍历对于二叉树的遍历顺序是一样的,都是先遍历左子树再遍历右子树,不一样的是,取节点值的时机不同,前序遍历是在一开始就去了当前节点的值,而中序遍历是在递归遍历完了当前节点的左子树之后才取的值。

因此前序遍历的结果的值的顺序就是我们递归二叉树的顺序,因为前序遍历一递归到节点就取值,因此前序遍历的第一个元素一定是根节点。

而中序遍历,用我的话来说,就是把二叉树压扁,说起来比较抽象。可以参考下面的动图看一看。

因为二叉树压扁之后就是中序遍历的结果,所以结果里某个节点的左边的节点,都在这个节点的左子树上,在这节点右边的节点,都在这个节点的右子树上。

大概懂了两种遍历结果的特点之后,我们来分析如何通过这俩结果来构造一棵二叉树。

我们就以105题的示例一为例。        

中序遍历的结果是:

[ 9 , 3 , 15 , 20 , 7]

前序遍历的结果是:

[ 3 , 9 , 20 , 15 , 7 ]

根据我们刚才说的,前序遍历的结果的第一个元素就是根节点。因此我们构造出的二叉树的根节点的值就是前序遍历的第一个值:3。

而3在中序遍历中,将结果分为了两半,【9】和【15,20,7】。

又根据我们刚才说的,【9】在原本3的左边,所以9在3的左子树,【15,20,7】在3的右边,所以它们仨在3的右子树上。

3的左子树就9一个节点,所以我们可以知道根节点的左子树节点的值就是9,那么问题在于右子树节点的值,有三个备选的值都在右子树上,那么哪一个值是根节点的右子树的根节点的值呢?

这时候我们就需要看前序遍历了,按照顺序来看,开头的3和9我们都用过了,那么接下来轮到的是20,所以根节点的右子树节点的值就是20。

20在中序遍历中,将剩余的结果又分为了两半,是15和7,分别是20的左右子树。至此遍历完毕,我们也就构造完了二叉树。

我们知道如何用前序遍历和中序遍历的结果构造二叉树之后我们再回过头来看看今天的每日一题。

前序遍历和中序遍历相信大家都懂,我们先分别将两个结果集的每个元素之间用一个特殊符号来连接起来,代码中我用的是‘#’,再用另一个特殊符号来连接两个结果集,代码中我用的是‘/’。如此我们就将一棵二叉树序列化了。

反序列化的话,我们只需将前序遍历的结果和中序遍历的结果从序列化后的字符串中提取出来,然后直接使用105题的代码就可以,我在代码中也是这么做的。

我这种做法没有利用到搜索二叉树的特性,并且代码又臭又长,所以仅供大家参考,提供一种思路,可以参考下面的动图来体会一下怎么通过前序和中序遍历来构造二叉树。

代码:

class Codec {
public:vector<int>cache;void qianxv(TreeNode* root){    //前序遍历if(root==nullptr) return;cache.push_back(root->val);qianxv(root->left);qianxv(root->right);}void zhongxv(TreeNode* root){   //中序遍历if(root==nullptr) return;zhongxv(root->left);cache.push_back(root->val);zhongxv(root->right);}// Encodes a tree to a single string.string serialize(TreeNode* root) {  //将前序和中序的结果拼接cache.clear();qianxv(root);string res="";for(auto c:cache) res+="#"+to_string(c);res+='/';   //中间用'/'分隔cache.clear();zhongxv(root);for(auto c:cache) res+="#"+to_string(c);return res;}//力扣105题,前序与中序构造二叉树TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(inorder.size()==0) return nullptr;TreeNode* res=new TreeNode(preorder[0]);    //根节点一定是前序遍历的第一个int index=0;for(;index<inorder.size();index++){if(inorder[index]==preorder[0]) break;  //找到根节点在中序遍历的位置}   preorder.erase(preorder.begin());   //移除前序遍历第一个节点vector<int>left,right;//中序遍历的位置的左边是当前节点的左子树if(index!=0) left=vector<int>(inorder.begin(),inorder.begin()+index);//中序遍历的位置的右边是当前节点的右子树  if(index!=inorder.size()-1) right=vector<int>(inorder.begin()+index+1,inorder.end());//传入更新过的前序遍历和中序遍历来构造左右子树res->left=buildTree(preorder,left);res->right=buildTree(preorder,right);return res;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {vector<int>preorder,inorder;int index=0;while(data[index]!='/'){if(data[index]=='#'){string temp="";index++;while(data[index]!='#'&&data[index]!='/'){temp+=data[index];index++;}preorder.push_back(stoi(temp));}}index++;while(index<data.size()){if(data[index]=='#'){string temp="";index++;while(index<data.size()&&data[index]!='#'){temp+=data[index];index++;}inorder.push_back(stoi(temp));}}return buildTree(preorder,inorder);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/121574.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于单片机的万年历温度无线传输控制系统系统

一、系统方案 本设计采用DS1302采集年月日时分秒&#xff0c;DS18B20采集温度值&#xff0c;按键设置温度报警上下限&#xff0c;实际测量温度低于下限或高于上限&#xff0c;蜂鸣器报警&#xff0c;同时将测量温度上传到蓝牙助手。 二、硬件设计 原理图如下&#xff1a; 三…

基于Matlab实现频谱分析(附上源码+数据集)

Matlab是一个功能强大的数值计算和科学计算软件&#xff0c;可以用于频谱分析。频谱分析是一种信号处理技术&#xff0c;用于将时域信号转换为频域信号&#xff0c;以便更好地理解信号的频率特性。本文将介绍使用Matlab实现频谱分析的方法。 文章目录 部分源码完整源码数据集下…

Mysql高阶语句(二)

一、设置别名&#xff08;alias ——>as&#xff09; 在 MySQL 查询时&#xff0c;当表的名字比较长或者表内某些字段比较长时&#xff0c;为了方便书写或者 多次使用相同的表&#xff0c;可以给字段列或表设置别名。使用的时候直接使用别名&#xff0c;简洁明了&#xff0…

【微服务部署】三、Jenkins+Maven插件Jib一键打包部署SpringBoot应用Docker镜像步骤详解

前面我们介绍了K8SDockerMaven插件打包部署SpringCloud微服务项目&#xff0c;在实际应用过程中&#xff0c;很多项目没有用到K8S和微服务&#xff0c;但是用到了Docker和SpringBoot&#xff0c;所以&#xff0c;我们这边介绍&#xff0c;如果使用Jenkinsjib-maven-plugin插件打…

无涯教程-Android - List fragments函数

框架的ListFragment的静态库支持版本&#xff0c;用于编写在Android 3.0之前的平台上运行的应用程序&#xff0c;在Android 3.0或更高版本上运行时,仍使用此实现。 List fragment 的基本实现是用于创建fragment中的项目列表 List in Fragments 示例 本示例将向您说明如何基于…

LSM树详解

LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象&#xff0c;事实上&#xff0c;LSM树并不像B树、红黑树一样是一颗严格的树状数据结构&#xff0c;它其实是一种存储结构&#xff0c;目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。 LSM树的核…

Redis-Cluster集群操作--添加节点、删除节点

一、环境部署 部署好Redis-Cluster集群&#xff0c;参考上个本人的博客&#xff1a;Redis-Cluster集群的部署&#xff08;详细步骤&#xff09;_是胡也是福的博客-CSDN博客 新准备一台机器&#xff0c;修改主机名&#xff0c;关闭防火墙和selinux&#xff0c;参考&#xff1a…

Jupyter Notebook 好用在哪?

Jupyter Notebook 是一个 Web 应用程序&#xff0c;便于创建和共享文学化程序文档&#xff0c;支持实时代码、数学方程、可视化和 Markdown&#xff0c;其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前&#xff0c;数据挖掘领域中最热门的比赛 Kaggle 里的资…

EI、Scopus双检索| 2023年第四届自动化、机械与设计工程国际会议

会议简介 Brief Introduction 2023年第四届自动化、机械与设计工程国际会议&#xff08;SAMDE 2023&#xff09; 会议时间&#xff1a;2023年12月8 -10日 召开地点&#xff1a;中国南京 大会官网&#xff1a;www.samde.org 机械设计制造及其自动化学科在国民经济中处于极其重要…

数学建模--最短路径算法的Python实现

目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 #最短路径算法 #针对有向图的最短路径问题,我们有很多的算法能解决. """ 目前主流算法如下所示: Dijkstra算法:Dijkstra算法是一种单源最短路径算法,用于计算从起点到其它所有节点的最短…

java八股文面试[多线程]——线程间通信方式

多个线程在并发执行的时候&#xff0c;他们在CPU中是随机切换执行的&#xff0c;这个时候我们想多个线程一起来完成一件任务&#xff0c;这个时候我们就需要线程之间的通信了&#xff0c;多个线程一起来完成一个任务&#xff0c;线程通信一般有4种方式&#xff1a; 通过 volat…

TypeScript_树结构-BST树

树结构 树的特点 树通常有一个根。连接着根的是树干树干到上面之后会进行分叉成树枝&#xff0c;树枝还会分又成更小的树枝在树枝的最后是叶子 树的抽象 树可以模拟生活中的很多场景&#xff0c;比如&#xff1a;公司组织架构、家谱、DOM Tree、电脑文件夹架构 优秀的哈希函…

STM32 SPI对存储芯片发送写是能命令后一直忙等待

我采用CUBE配置的SPI外设&#xff0c;对NSS引脚选择了硬件输出&#xff0c;这种方式对读取命令没有影响&#xff0c;但是对写命令有&#xff0c;当我发送写是能命令后&#xff0c;读取状态寄存器的值一直都是忙&#xff0c;我猜测这可能是硬件控制NSS引脚后&#xff0c;对于HAL…

如何用Jmeter编写脚本压测?

随着商业业务不断扩张&#xff0c;调用adsearch服务频率越来越高&#xff0c;所以这次想做个压测&#xff0c;了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具&#xff0c;压测思路如图&#xff1a; 一、日志入参 日志选取的adsearch 的 getads部分…

WEB APIs day6

一、正则表达式 RegExp是正则表达式的意思 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" co…

二叉树的介绍及二叉树的链式结构的实现(C语言版)

前言 二叉树是一种特殊的树&#xff0c;它最大的度为2&#xff0c;每个节点至多只有两个子树。它是一种基础的数据结构&#xff0c;后面很多重要的数据结构都是依靠它来进行实现的。了解并且掌握它是很重要的。 目录 1.二叉树的介绍 1.1概念 1.2现实中的二叉树 1.3特殊的二叉…

QCAD for Mac免费下载:卓越的2D辅助设计工具

QCAD是一款功能强大的2D辅助设计画图软件&#xff0c;现已适配Mac系统&#xff0c;为Mac用户提供了便捷高效的设计工具。 QCAD提供了丰富的绘图功能&#xff0c;可以轻松绘制各种平面图形&#xff0c;包括直线、圆、椭圆、弧线等。 同时&#xff0c;QCAD还支持多种绘图工具&am…

树莓 LUMA-OLED.EXAMPLE使用

详细介绍在文件目录下的README.rst中 第一步 $ sudo usermod -a -G i2c,spi,gpio pi //好像没什么用 $ sudo apt install python3-dev python3-pip python3-numpy libfreetype6-dev libjpeg-dev build-essential //安装依赖包&#xff0c;树莓派中好像已经有了 $ sudo a…

linux信号量

通过学习linux的信号量&#xff0c;对linux的信号量进行了编程。

iPhone 15 Pro展示设计:7项全新变化呈现

我们不应该再等iPhone 15 Pro在苹果9月12日的“Wonderlust”活动上发布了&#xff0c;而且可能会有很多升级。有传言称&#xff0c;iPhone 15 Pro将是自iPhone X以来最大的飞跃&#xff0c;这要归功于大量的新变化&#xff0c;从带有更薄边框的新钛框架到顶级A17仿生芯片和动作…