C++算法:二叉树的序列化与反序列化

#题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。
示例 1:
输入:root = [1,2,3,null,null,4,5]
输出:[1,2,3,null,null,4,5]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[1,2]
提示:
树中结点数在范围 [0, 10^4] 内
-1000 <= Node.val <= 1000

2023年6月版本

class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {auto str = serializeInner(root);//std::cout << str << std::endl;return str;
}// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {int iPos = 0;return deserialize(data, iPos);
}

private:
string serializeInner(TreeNode* root) {
if (nullptr == root)
{
return “()”;
}
return “(” + std::to_string(root->val) + serialize(root->left) + serialize(root->right) + “)”;
}
TreeNode* deserialize(string data,int& iPos)
{
if (iPos >= data.length())
{
return nullptr;
}
iPos++;
if ( ‘)’ == data[iPos])
{
iPos ++;
return nullptr;
}
int iValue = 0;
int iSign = 1;
if (‘-’ == data[iPos])
{
iSign = -1;
iPos++;
}
while (::isdigit(data[iPos]))
{
iValue = iValue * 10 + data[iPos] - ‘0’;
iPos++;
}
iValue = iSign;
TreeNode
p = new TreeNode(iValue);
p->left = deserialize(data, iPos);
p->right = deserialize(data, iPos);
iPos++;
return p;
}
};

2023年8月版

class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector v;
std::queue<TreeNode*> que;
que.emplace(root);
while (que.size())
{
const auto cur = que.front();
que.pop();
if (nullptr == cur)
{
v.emplace_back(“”);
}
else
{
v.emplace_back(std::to_string(cur->val));
que.emplace(cur->left);
que.emplace(cur->right);
}
}
while (v.size() && (“” == v.back()))
{
v.pop_back();
}
string strRet;
for (const auto& s : v)
{
strRet += s + “,”;
}
return strRet;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector v;
int left = 0;
for (int i = 0; i < data.size(); i++)
{
if (‘,’ == data[i])
{
v.emplace_back(data.substr(left, i - left));
left = i + 1;
}
}
if (0 == v.size())
{
return nullptr;
}
TreeNode* root = new TreeNode(atoi(v[0].c_str()));
std::queue<TreeNode*> que;
que.emplace(root);
int i = 1;
while ((i < v.size()) && que.size())
{
const auto cur = que.front();
que.pop();
if (“” != v[i])
{
cur->left = new TreeNode(atoi(v[i].c_str()));
que.emplace(cur->left);
}
i++;
if (i >= v.size())
{
break;
}
if (“” != v[i])
{
cur->right = new TreeNode(atoi(v[i].c_str()));
que.emplace(cur->right);
}
i++;
}
return root;
}

};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

鄙人想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨家名称的来源:有所得以墨记之。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

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

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

相关文章

花生好车基于 KubeSphere 的微服务架构实践

公司简介 花生好车成立于 2015 年 6 月&#xff0c;致力于打造下沉市场汽车出行解决方案第一品牌。通过自建直营渠道&#xff0c;瞄准下沉市场&#xff0c;现形成以直租、批售、回租、新能源汽车零售&#xff0c;四大业务为核心驱动力的汽车新零售平台&#xff0c;目前拥有门店…

[自定义 Vue 组件] 小尾巴 Logo 组件 TailLogo

文字归档于&#xff1a;https://www.yuque.com/u27599042/coding_star/apt6y731ybmxgu5g 组件效果 组件依赖 自定义字符串工具函数 stringIsNull https://www.yuque.com/u27599042/coding_star/slncupw7un3ce7cb import {stringIsNull} from "/utils/string_utils.js&q…

移动App安全检测的必要性,app安全测试报告的编写注意事项

随着移动互联网的迅猛发展&#xff0c;移动App已经成为人们日常生活中不可或缺的一部分。然而&#xff0c;虽然App给我们带来了便利和乐趣&#xff0c;但也伴随着一些潜在的安全风险。黑客、病毒、恶意软件等威胁着用户的隐私和财产安全&#xff0c;因此进行安全检测就显得尤为…

acwing算法基础之数据结构--KMP算法

目录 1 知识点2 模板 1 知识点 KMP算法已经集成到string类型的find()方法了&#xff0c; 但这里我们不用这个&#xff0c;我们自己来实现这个方法。 KMP算法的关键步骤&#xff1a; p[N]表示输入模式串&#xff0c;求取该模式串的ne[]数组。ne[i]表示前缀等于后缀的长度&…

UE4 UltrDynamicSky与场景物体进行交互

找到材质 找到其最父类的材质 把这个拖过去连上即可

TikTok Shop新结算政策:卖家选择权加强,电商市场蓄势待发

据悉&#xff0c;从2023年11月1日开始&#xff0c;TikTok Shop将根据卖家的店铺表现来应用3种不同类型的结算期&#xff0c;其中&#xff0c;标准结算期&#xff1a;资金交收期为8个日历日&#xff1b;快速结算期&#xff1a;资金交收期为3个日历日&#xff1b;延长结算期&…

尚硅谷Flink(完)FlinkSQL

&#x1f9d9;FlinkSQL&#x1f3c2;&#x1f93a; Table API 和 SQL 是最上层的 API&#xff0c;在 Flink 中这两种 API 被集成在一起&#xff0c;SQL 执行的对象也是Flink 中的表&#xff08;Table&#xff09;&#xff0c;所以我们一般会认为它们是一体的。 SQL API 是基于…

Python学习基础笔记七十七——json序列化

客户端和服务端之间需要交换数据才能完成各种功能。 假设 服务端程序都是用Python语言开发的话&#xff0c;那么 服务端从数据库中获取的最近的交易列表&#xff0c;可能就是像下面这样的一个Python列表对象&#xff1a; historyTransactions [{time : 20170101070311, #…

mysql过期数据的清理方案(Java/springboot+mybatis)

比如说现在数据库表信息增加的很快&#xff0c;然后我们需要对每个表设置过期删除策略&#xff1b; 大概思路就是&#xff1a;定时任务调度&#xff0c;给每个表制定sql&#xff0c;然后执行删除数据的sql //删除一个月前的数据 delete FROM test_info WHERE create_time <…

C++初阶--C++入门(2)

C入门&#xff08;1&#xff09;链接入口 文章目录 内联函数auto关键字注意事项 基于范围的for循环(C11)nullptr 内联函数 以inline修饰的函数叫做内联函数&#xff0c;编译时C编译器会在调用内联函数的地方展开&#xff0c;没有函数调用建立栈帧的开销&#xff0c;内联函数提…

ND协议——无状态地址自动配置 (SLAAC)

参考学习&#xff1a;计算机网络 | 思科网络 | 无状态地址自动配置 (SLAAC) | 什么是SLAAC_瘦弱的皮卡丘的博客-CSDN博客 与 IPv4 类似&#xff0c;可以手动或动态配置 IPv6 全局单播地址。但是&#xff0c;动态分配 IPv6 全局单播地址有两种方法&#xff1a; 如图所示&#…

『C++ - STL』之优先级队列( priority_queue )

文章目录 前言优先级队列的结构优先级队列的模拟实现仿函数 最终代码 前言 什么是优先级队列&#xff0c;从该名中可以知道他一定有队列的一定属性&#xff0c;即先入先出(LILO)&#xff0c;而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进…

移动设备管理对企业IT 安全的增强

移动设备管理 &#xff08;MDM&#xff09; 是通过定义策略和部署安全控制&#xff08;如移动应用程序管理、移动内容管理和条件 Exchange 访问&#xff09;来管理移动设备的过程。 完整的MDM解决方案可以管理在Android&#xff0c;iOS&#xff0c;Windows&#xff0c;macOS&a…

【论文解读】单目3D目标检测 DD3D(ICCV 2021)

本文分享单目3D目标检测&#xff0c;DD3D 模型的论文解读&#xff0c;了解它的设计思路&#xff0c;论文核心观点&#xff0c;模型结构&#xff0c;以及效果和性能。 一、DD3D简介 DD3D是一种端到端、单阶段的单目3D目标检测方法&#xff0c;它在训练时用到了点云数据&#xf…

索引失效的几种情况

目录 数据准备&#xff1a; 1、查询条件中有or&#xff0c;索引会失效&#xff1b; 2、like查询以%开头 3、如果类型为字符串&#xff0c;查询条件中数据需用引号引起来&#xff0c;否则不走索引&#xff1b; 4、索引列上参与计算会导致索引失效 5、违背最左匹配原则 6、…

[Hive] explode

在 Hive 中&#xff0c;explode 函数用于将数组&#xff08;Array&#xff09;或者Map类型的列拆分成多行&#xff0c; 每个元素或键值对为一行。这允许我们在查询中对数组或 Map 进行扁平化操作。 下面是使用 explode 函数的示例&#xff1a; 假设我们有一个包含数组字段的表…

面试知识点--基础篇

文章目录 前言一、排序1. 冒泡排序2. 选择排序3. 插入排序4. 快速单边循环排序5. 快速双边循环排序6. 二分查找 二、集合1.List2.Map 前言 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、排序 1. 冒泡排序 冒泡排序就是把小的元素往前调或者把大…

flutter 创建插件

资料&#xff1a; flutter与原生通信的方式简介 - 简书 完整流程 Flutter 集成 Golang 多语言跨端开发基础案例 - 知乎 https://www.cnblogs.com/webabcd/p/flutter_lib_plugin_plugin_ios.html 步骤1、创建插件 我创建的插件名字是konnect_im_sdk 选择的语言是 java和swi…

22款奔驰S400L升级原厂360全景影像 倒车更加的安全

您是否经历过这种场面呢&#xff1f; 停车位&#xff0c;狭窄障碍停车困难 避免盲区&#xff0c;倒车盲区危及生命安全 狭窄路段&#xff0c;无法判断是否安全通过 视角盲区&#xff0c;小孩站在视野盲区看不到&#xff0c;Xjh15863 360度无缝3D全车可见&#xff0c;解决各…

uniapp开发多端应用项目时的常见跨端兼容处理

一、跨端兼容 每个端有每个端的特点&#xff0c;有的能被抹平&#xff0c;有的不可能被抹平。 跨端&#xff0c;不是把web的习惯迁移到全平台。而是按照uni的写法&#xff0c;然后全平台使用。 按照uniapp规范开发可以保证多平台兼容&#xff0c;但每个平台有自己的一些特性。…