每日一题——序列化二叉树
序列化二叉树
- BM39 序列化二叉树
- 题目描述
- 序列化
- 反序列化
- 示例
- 示例1
- 示例2
- 解题思路
- 序列化过程
- 反序列化过程
- 代码实现
- 代码说明
- 复杂度分析
- 总结
BM39 序列化二叉树
题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式转换为字符串格式,而反序列化则是根据字符串重建出原二叉树。
序列化
二叉树的序列化(Serialize)是指将二叉树转换为字符串,通常我们使用层序遍历的方式将树的节点值逐个保存。在序列化的过程中,用某种符号表示空节点(如#),例如:层序序列化的结果为"{1,2,3,#,#,6,7}"。
反序列化
二叉树的反序列化(Deserialize)是指根据序列化后的字符串重建出二叉树。例如,给定序列化字符串"{1,2,3,#,#,6,7}",我们可以重新构造出与原二叉树相同的树结构。
示例

示例1
输入:
{1,2,3,#,#,6,7}
返回值:
{1,2,3,#,#,6,7}
示例2

输入:
{8,6,10,5,7,9,11}
返回值:
{8,6,10,5,7,9,11}
解题思路
序列化过程
- 使用层序遍历的方式遍历二叉树。
- 将每个节点的值转化为字符串,并用
#表示空节点。 - 将结果以逗号连接形成最终的字符串。
反序列化过程
- 将序列化后的字符串按逗号分割。
- 按照层序的顺序,逐个构建二叉树的节点。
- 使用队列来辅助构建树的结构,按照层序遍历的方式将节点插入到对应的位置。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义二叉树节点
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 定义队列节点
typedef struct QueueNode {struct TreeNode* treeNode;struct QueueNode* next;
} QueueNode;// 定义队列
typedef struct {QueueNode* front;QueueNode* rear;
} Queue;// 创建队列
Queue* createQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));q->front = q->rear = NULL;return q;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == NULL;
}// 入队
void enqueue(Queue* q, struct TreeNode* node) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->treeNode = node;newNode->next = NULL;if (q->rear != NULL) {q->rear->next = newNode;}q->rear = newNode;if (q->front == NULL) {q->front = newNode;}
}// 出队
struct TreeNode* dequeue(Queue* q) {if (isEmpty(q)) {return NULL;}QueueNode* temp = q->front;struct TreeNode* node = temp->treeNode;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return node;
}// 释放队列
void freeQueue(Queue* q) {while (!isEmpty(q)) {dequeue(q);}free(q);
}// 序列化二叉树
char* Serialize(struct TreeNode* root) {if (root == NULL) {return "#";}Queue* q = createQueue();enqueue(q, root);char* result = (char*)malloc(10000 * sizeof(char)); // 假设字符串长度足够char* buffer = (char*)malloc(100 * sizeof(char));int len = 0;while (!isEmpty(q)) {struct TreeNode* node = dequeue(q);if (node == NULL) {len += sprintf(result + len, "#,");} else {len += sprintf(result + len, "%d,", node->val);enqueue(q, node->left);enqueue(q, node->right);}}// 去掉最后一个逗号if (len > 0 && result[len - 1] == ',') {result[len - 1] = '\0';} else {result[len] = '\0';}free(buffer);freeQueue(q);return result;
}// 反序列化二叉树
struct TreeNode* Deserialize(char* data) {if (strcmp(data, "#") == 0) {return NULL;}char* token = strtok(data, ",");struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = atoi(token);root->left = root->right = NULL;Queue* q = createQueue();enqueue(q, root);while ((token = strtok(NULL, ",")) != NULL) {struct TreeNode* parent = dequeue(q);if (strcmp(token, "#") != 0) {struct TreeNode* leftNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));leftNode->val = atoi(token);leftNode->left = leftNode->right = NULL;parent->left = leftNode;enqueue(q, leftNode);}token = strtok(NULL, ",");if (token == NULL) {break;}if (strcmp(token, "#") != 0) {struct TreeNode* rightNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));rightNode->val = atoi(token);rightNode->left = rightNode->right = NULL;parent->right = rightNode;enqueue(q, rightNode);}}freeQueue(q);return root;
}
代码说明
- 队列实现:为了方便按层次遍历二叉树,我们使用队列来存储树的节点。
- 序列化函数
Serialize:使用层序遍历对树进行遍历,将节点值加入到结果字符串中。如果节点为空,则用#表示。 - 反序列化函数
Deserialize:将序列化后的字符串按逗号分割,依次创建节点并建立左右子树。
复杂度分析
- 时间复杂度:
O(n),其中n是树的节点数。每个节点在序列化和反序列化过程中只被访问一次。 - 空间复杂度:
O(n),需要存储队列中的节点以及序列化后的字符串。
总结
本题考察了二叉树的序列化与反序列化,使用层序遍历来实现序列化和反序列化的方法,保证了在时间和空间复杂度上都能满足要求。这题的整体难度还是不小的,但是最主要的是队列的实现,这个完成,任务就完成一半。至于后面函数的实现,就是研究递归了。
相关文章:
每日一题——序列化二叉树
序列化二叉树 BM39 序列化二叉树题目描述序列化反序列化 示例示例1示例2 解题思路序列化过程反序列化过程 代码实现代码说明复杂度分析总结 BM39 序列化二叉树 题目描述 请实现两个函数,分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式…...
Transformer+vit原理分析
目录 一、Transformer的核心思想 1. 自注意力机制(Self-Attention) 2. 多头注意力(Multi-Head Attention) 二、Transformer的架构 1. 整体结构 2. 编码器层(Encoder Layer) 3. 解码器层(Decoder…...
「AI学习笔记」深度学习的起源与发展:从神经网络到大数据(二)
深度学习(DL)是现代人工智能(AI)的核心之一,但它并不是一夜之间出现的技术。从最初的理论提出到如今的广泛应用,深度学习经历了几乎一个世纪的不断探索与发展。今天,我们一起回顾深度学习的历史…...
【漫话机器学习系列】069.哈达马乘积(Hadamard Product)
哈达马乘积(Hadamard Product) 哈达马乘积(Hadamard Product)是两个矩阵之间的一种元素级操作,也称为逐元素乘积(Element-wise Product)。它以矩阵的对应元素相乘为规则,生成一个新…...
2025一区新风口:小波变换+KAN!速占!
今天给大家分享一个能让审稿人眼前一亮,好发一区的idea:小波变换KAN! 一方面:KAN刚中稿ICLR25,正是风口上,与小波变换的结合还处于起步阶段,正是红利期,创新空间广阔。 另一方面&a…...
相同的树及延伸题型(C语言详解版)
从LeetCode 100和101看二叉树的比较与对称性判断 今天要讲的是leetcode100.相同的树,并且本文章还会讲到延伸题型leetcode101.对称二叉树。本文章编写用的是C语言,大家主要是学习思路,学习过后可以自己点击链接测试,并且做一些对…...
【Redis】 String 类型的介绍和常用命令
1. 介绍 Redis 中的 key 都是字符串类型Redis 中存储字符串是完全按照二进制流的形式保存的,所以 Redis 是不处理字符集编码的问题,客户端传入的命令中使用的是什么编码就采用什么编码,使得 Redis 能够处理各种类型的数据,包括文…...
LLM - 大模型 ScallingLaws 的设计 100B 预训练方案(PLM) 教程(5)
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/145356022 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 Scaling Laws (缩放法则) 是大模型领域中,用于描述 模型性能(Loss) 与…...
Docker/K8S
文章目录 项目地址一、Docker1.1 创建一个Node服务image1.2 volume1.3 网络1.4 docker compose 二、K8S2.1 集群组成2.2 Pod1. 如何使用Pod(1) 运行一个pod(2) 运行多个pod 2.3 pod的生命周期2.4 pod中的容器1. 容器的生命周期2. 生命周期的回调3. 容器重启策略4. 自定义容器启…...
32、【OS】【Nuttx】OSTest分析(1):stdio测试(二)
背景 接上篇wiki 31、【OS】【Nuttx】OSTest分析(1):stdio测试(一) 继续stdio测试的分析,上篇讲到标准IO端口初始化,单从测试内容来说其实很简单,没啥可分析的,但这几篇…...
git push到远程仓库时无法推送大文件
一、错误 remote: Error: Deny by project hooks setting ‘default’: size of the file ‘scientific_calculator’, is 164 MiB, which has exceeded the limited size (100 MiB) in commit ‘4c91b7e3a04b8034892414d649860bf12416b614’. 二、原因 本地提交过大文件&am…...
Vue.js路由管理与自定义指令深度剖析
Vue.js 是一个强大的前端框架,提供了丰富的功能来帮助开发者构建复杂的单页应用(SPA)。本文将详细介绍 Vue.js 中的自定义指令和路由管理及导航守卫。通过这些功能,你可以更好地控制视图行为和应用导航,从而提升用户体验和开发效率。 1 自定义指令详解 1.1 什么是自定义…...
NVIDIA GPU介绍:概念、序列、核心、A100、H100
概述 入职一家大模型领域创业公司,恶补相关知识。 概念 一些概念: HPC:High Performance Computing,高性能计算SoC:System on Chip,单片系统FLOPS:Floating Point Operations Per Second&am…...
【PyTorch】6.张量运算函数:一键开启!PyTorch 张量函数的宝藏工厂
目录 1. 常见运算函数 个人主页:Icomi 专栏地址:PyTorch入门 在深度学习蓬勃发展的当下,PyTorch 是不可或缺的工具。它作为强大的深度学习框架,为构建和训练神经网络提供了高效且灵活的平台。神经网络作为人工智能的核心技术&…...
C语言练习(31)
有5个学生,每个学生有3门课程的成绩,从键盘输入以上数据(包括学号、姓名、3门课程成绩),计算出平均成绩,将原有数据和计算出的平均分数存放在磁盘文件stud中。 设5名学生的学号、姓名和3门课程成绩如下&am…...
什么是长短期记忆网络?
一、概念 长短期记忆网络(Long Short-Term Memory, LSTM)是一种特殊的循环神经网络(RNN),旨在解决标准RNN在处理长序列时的梯度消失和梯度爆炸问题。LSTM通过引入三个门(输入门、遗忘门和输出门)…...
git中有关old mode 100644、new mode 10075的问题解决小结
在 Git 版本控制系统中,文件权限变更是一种常见情况。当你看到类似 old mode 100644 和 new mode 100755 的信息时,这通常表示文件的权限发生了变化。本文将详细解析这种情况,并提供解决方法和注意事项。 问题背景 在 Git 中,文…...
Jenkins上生成的allure report打不开怎么处理
目录 问题背景: 原因: 解决方案: Jenkins上修改配置 通过Groovy脚本在Script Console中设置和修改系统属性 步骤 验证是否清空成功 进一步的定制 也可以使用Nginx去解决 使用逆向代理服务器Nginx: 通过合理调整CSP配置&a…...
JSR303校验教学
1、什么是JSR303校验 JSR是Java Specification Requests的缩写,意思是Java 规范提案。是指向JCP(Java Community Process)提出新增一个标准化技术规范的正式请求。任何人都可以提交JSR,以向Java平台增添新的API和服务。JSR已成为Java界的一个重要标准。…...
使用DeepSeek技巧:提升内容创作效率与质量
一、引言 在当今快节奏的数字时代,内容创作的需求不断增加,无论是企业营销、个人博客还是学术研究,高效且高质量的内容生成变得至关重要。DeepSeek作为一款先进的人工智能写作助手,凭借其强大的语言生成能力,为创作者…...
claw-diary:基于Git与Markdown的开发者命令行日记工具
1. 项目概述:一个面向开发者的命令行日记工具最近在折腾个人知识管理,发现市面上的日记软件要么太重,要么太花哨,要么就是数据被锁在云端,让人不太放心。作为一个常年与终端为伴的开发者,我一直在想&#x…...
Wand-Enhancer:三步解锁WeMod Pro功能的终极免费方案
Wand-Enhancer:三步解锁WeMod Pro功能的终极免费方案 【免费下载链接】Wand-Enhancer Advanced UX and interoperability extension for Wand (WeMod) app 项目地址: https://gitcode.com/gh_mirrors/we/Wand-Enhancer 还在为WeMod专业版的订阅费用而烦恼吗&…...
TCP专栏-3.三次握手
什么是三次握手三次握手是指,在建立TCP连接时,客户端和服务端总共会发送三个数据包。只有三个数据包都发送成功后,TCP连接才会建立成功。否则,丢失任何一个包,都会导致连接建立失败。发送三个数据包的过程,…...
怎样高效配置Python语法检查:专业开发者的实战指南
怎样高效配置Python语法检查:专业开发者的实战指南 【免费下载链接】language_tool_python a free, non-AI python grammar checker 📝✅ 项目地址: https://gitcode.com/gh_mirrors/la/language_tool_python LanguageTool Python是一个功能强大的…...
避坑指南:ESP32 ADC采样时这些操作会让数据‘丢帧’(WiFi冲突、看门狗、串口打印)
ESP32 ADC采样稳定性实战:规避数据丢失的6个关键策略 在物联网和嵌入式开发领域,ESP32因其出色的无线连接能力和丰富的外设资源成为热门选择。但当开发者将其ADC(模数转换器)功能用于高精度数据采集时,常常会遇到采样数…...
独立开发者如何借助Taotoken模型广场快速选型与验证创意
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 独立开发者如何借助Taotoken模型广场快速选型与验证创意 对于独立开发者或小型团队而言,验证一个AI产品创意的核心挑战…...
基于树莓派与AstroPrint搭建无线3D打印控制中心实战指南
1. 项目概述:为什么需要无线3D打印控制?如果你和我一样,是个喜欢折腾3D打印机的创客或爱好者,那你肯定经历过这样的场景:为了打印一个模型,需要先在电脑上用切片软件生成G-code文件,然后找到读卡…...
JetBrains IDE试用期重置技术全解析:从原理到实战的开发者指南
JetBrains IDE试用期重置技术全解析:从原理到实战的开发者指南 【免费下载链接】ide-eval-resetter 项目地址: https://gitcode.com/gh_mirrors/id/ide-eval-resetter 在JetBrains IDE生态系统中,试用期管理是每个开发者都会面临的实际问题。ide…...
npm ERR! 401 认证失败全解析:从私有包权限到 .npmrc 配置的实战排错指南
1. 遇到npm ERR! 401怎么办?先别慌 最近在项目里执行npm install时,突然蹦出个npm ERR! 401 Unauthorized的错误,相信不少前端开发者都遇到过这个烦人的问题。我第一次碰到时也是一头雾水,明明昨天还能正常安装依赖,怎…...
【BMC】OpenBMC开发进阶:从零构建自定义Layer与集成应用
1. OpenBMC自定义Layer开发入门 第一次接触OpenBMC的开发者常会困惑:如何在现有框架下快速集成自己的硬件平台和应用?这就像装修房子,OpenBMC提供了毛坯房(基础框架),我们需要根据户型(硬件&…...
