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

每日一题——序列化二叉树

序列化二叉树

  • 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}

解题思路

序列化过程

  1. 使用层序遍历的方式遍历二叉树。
  2. 将每个节点的值转化为字符串,并用#表示空节点。
  3. 将结果以逗号连接形成最终的字符串。

反序列化过程

  1. 将序列化后的字符串按逗号分割。
  2. 按照层序的顺序,逐个构建二叉树的节点。
  3. 使用队列来辅助构建树的结构,按照层序遍历的方式将节点插入到对应的位置。

代码实现

#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;
}

代码说明

  1. 队列实现:为了方便按层次遍历二叉树,我们使用队列来存储树的节点。
  2. 序列化函数 Serialize:使用层序遍历对树进行遍历,将节点值加入到结果字符串中。如果节点为空,则用#表示。
  3. 反序列化函数 Deserialize:将序列化后的字符串按逗号分割,依次创建节点并建立左右子树。

复杂度分析

  • 时间复杂度:O(n),其中n是树的节点数。每个节点在序列化和反序列化过程中只被访问一次。
  • 空间复杂度:O(n),需要存储队列中的节点以及序列化后的字符串。

总结

本题考察了二叉树的序列化与反序列化,使用层序遍历来实现序列化和反序列化的方法,保证了在时间和空间复杂度上都能满足要求。这题的整体难度还是不小的,但是最主要的是队列的实现,这个完成,任务就完成一半。至于后面函数的实现,就是研究递归了。

相关文章:

每日一题——序列化二叉树

序列化二叉树 BM39 序列化二叉树题目描述序列化反序列化 示例示例1示例2 解题思路序列化过程反序列化过程 代码实现代码说明复杂度分析总结 BM39 序列化二叉树 题目描述 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式…...

Transformer+vit原理分析

目录 一、Transformer的核心思想 1. 自注意力机制&#xff08;Self-Attention&#xff09; 2. 多头注意力&#xff08;Multi-Head Attention&#xff09; 二、Transformer的架构 1. 整体结构 2. 编码器层&#xff08;Encoder Layer&#xff09; 3. 解码器层&#xff08;Decoder…...

「AI学习笔记」深度学习的起源与发展:从神经网络到大数据(二)

深度学习&#xff08;DL&#xff09;是现代人工智能&#xff08;AI&#xff09;的核心之一&#xff0c;但它并不是一夜之间出现的技术。从最初的理论提出到如今的广泛应用&#xff0c;深度学习经历了几乎一个世纪的不断探索与发展。今天&#xff0c;我们一起回顾深度学习的历史…...

【漫话机器学习系列】069.哈达马乘积(Hadamard Product)

哈达马乘积&#xff08;Hadamard Product&#xff09; 哈达马乘积&#xff08;Hadamard Product&#xff09;是两个矩阵之间的一种元素级操作&#xff0c;也称为逐元素乘积&#xff08;Element-wise Product&#xff09;。它以矩阵的对应元素相乘为规则&#xff0c;生成一个新…...

2025一区新风口:小波变换+KAN!速占!

今天给大家分享一个能让审稿人眼前一亮&#xff0c;好发一区的idea&#xff1a;小波变换KAN&#xff01; 一方面&#xff1a;KAN刚中稿ICLR25&#xff0c;正是风口上&#xff0c;与小波变换的结合还处于起步阶段&#xff0c;正是红利期&#xff0c;创新空间广阔。 另一方面&a…...

相同的树及延伸题型(C语言详解版)

从LeetCode 100和101看二叉树的比较与对称性判断 今天要讲的是leetcode100.相同的树&#xff0c;并且本文章还会讲到延伸题型leetcode101.对称二叉树。本文章编写用的是C语言&#xff0c;大家主要是学习思路&#xff0c;学习过后可以自己点击链接测试&#xff0c;并且做一些对…...

【Redis】 String 类型的介绍和常用命令

1. 介绍 Redis 中的 key 都是字符串类型Redis 中存储字符串是完全按照二进制流的形式保存的&#xff0c;所以 Redis 是不处理字符集编码的问题&#xff0c;客户端传入的命令中使用的是什么编码就采用什么编码&#xff0c;使得 Redis 能够处理各种类型的数据&#xff0c;包括文…...

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分析&#xff08;1&#xff09;&#xff1a;stdio测试&#xff08;一&#xff09; 继续stdio测试的分析&#xff0c;上篇讲到标准IO端口初始化&#xff0c;单从测试内容来说其实很简单&#xff0c;没啥可分析的&#xff0c;但这几篇…...

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

概述 入职一家大模型领域创业公司&#xff0c;恶补相关知识。 概念 一些概念&#xff1a; HPC&#xff1a;High Performance Computing&#xff0c;高性能计算SoC&#xff1a;System on Chip&#xff0c;单片系统FLOPS&#xff1a;Floating Point Operations Per Second&am…...

【PyTorch】6.张量运算函数:一键开启!PyTorch 张量函数的宝藏工厂

目录 1. 常见运算函数 个人主页&#xff1a;Icomi 专栏地址&#xff1a;PyTorch入门 在深度学习蓬勃发展的当下&#xff0c;PyTorch 是不可或缺的工具。它作为强大的深度学习框架&#xff0c;为构建和训练神经网络提供了高效且灵活的平台。神经网络作为人工智能的核心技术&…...

C语言练习(31)

有5个学生&#xff0c;每个学生有3门课程的成绩&#xff0c;从键盘输入以上数据&#xff08;包括学号、姓名、3门课程成绩&#xff09;&#xff0c;计算出平均成绩&#xff0c;将原有数据和计算出的平均分数存放在磁盘文件stud中。 设5名学生的学号、姓名和3门课程成绩如下&am…...

什么是长短期记忆网络?

一、概念 长短期记忆网络&#xff08;Long Short-Term Memory, LSTM&#xff09;是一种特殊的循环神经网络&#xff08;RNN&#xff09;&#xff0c;旨在解决标准RNN在处理长序列时的梯度消失和梯度爆炸问题。LSTM通过引入三个门&#xff08;输入门、遗忘门和输出门&#xff09…...

git中有关old mode 100644、new mode 10075的问题解决小结

在 Git 版本控制系统中&#xff0c;文件权限变更是一种常见情况。当你看到类似 old mode 100644 和 new mode 100755 的信息时&#xff0c;这通常表示文件的权限发生了变化。本文将详细解析这种情况&#xff0c;并提供解决方法和注意事项。 问题背景 在 Git 中&#xff0c;文…...

Jenkins上生成的allure report打不开怎么处理

目录 问题背景&#xff1a; 原因&#xff1a; 解决方案&#xff1a; Jenkins上修改配置 通过Groovy脚本在Script Console中设置和修改系统属性 步骤 验证是否清空成功 进一步的定制 也可以使用Nginx去解决 使用逆向代理服务器Nginx&#xff1a; 通过合理调整CSP配置&a…...

JSR303校验教学

1、什么是JSR303校验 JSR是Java Specification Requests的缩写&#xff0c;意思是Java 规范提案。是指向JCP(Java Community Process)提出新增一个标准化技术规范的正式请求。任何人都可以提交JSR&#xff0c;以向Java平台增添新的API和服务。JSR已成为Java界的一个重要标准。…...

使用DeepSeek技巧:提升内容创作效率与质量

一、引言 在当今快节奏的数字时代&#xff0c;内容创作的需求不断增加&#xff0c;无论是企业营销、个人博客还是学术研究&#xff0c;高效且高质量的内容生成变得至关重要。DeepSeek作为一款先进的人工智能写作助手&#xff0c;凭借其强大的语言生成能力&#xff0c;为创作者…...

React基础-第一章:React 简介与开发环境搭建

&#x1f4d8; 第一章&#xff1a;React 简介与开发环境搭建 1. 什么是 React&#xff1f; React 是一个由 Facebook&#xff08;现 Meta&#xff09;开发并维护的 前端 JavaScript 库&#xff0c;用于构建用户界面&#xff0c;尤其是 单页应用&#xff08;SPA&#xff09;。 ✅…...

Linux SSH身份验证全解析:从密码到证书的六种方法与实践指南

1. SSH身份验证&#xff1a;守护远程访问的第一道门在Linux世界里&#xff0c;SSH&#xff08;Secure Shell&#xff09;就是那把打开远程服务器大门的钥匙。无论是管理云服务器、部署应用&#xff0c;还是进行日常运维&#xff0c;我们几乎每天都在和它打交道。但很多人可能没…...

Diablo Edit2:终极暗黑破坏神2角色存档编辑器完全指南

Diablo Edit2&#xff1a;终极暗黑破坏神2角色存档编辑器完全指南 【免费下载链接】diablo_edit Diablo II Character editor. 项目地址: https://gitcode.com/gh_mirrors/di/diablo_edit 你是否厌倦了在暗黑破坏神2中反复刷装备&#xff1f;是否因为技能点分配错误而不…...

实测Taotoken在低功耗arm7设备上的API调用延迟与稳定性表现

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 实测Taotoken在低功耗arm7设备上的API调用延迟与稳定性表现 1. 测试背景与目的 在边缘计算或资源受限的嵌入式场景中&#xff0c;…...

不使用void HAL_TIM_Encoder_MspInit(TIM_HandleTypeDef* tim_encoderHandle)增强代码的层级结构注意事项

这是正常用cube Max生成的代码&#xff0c;这里以设置编码器为例。 GPIO初始化函数放在HAL_TIM_Encoder_MspInit这个回调函数中。代码正常运行/* TIM3 init function */ void MX_TIM3_Init(void) {TIM_Encoder_InitTypeDef sConfig {0};TIM_MasterConfigTypeDef sMasterConfig…...

单元幕墙组装检验标准

单元幕墙组装检验标准 1 范围 本标准规定了沈阳远大企业集团单元幕墙组装的检验项目、检验方法、检验工具、质量评定方法。 本标准适用于单元幕墙板块的组装检验。 2 规范性引用文件 下列文件中的条款通过本标准的引用而成为本标准的条款,凡是注日期的引用文件,其随后所…...

【DeepSeek MATH竞赛测试权威复盘】:20年AI评测专家独家拆解7大能力断层与提分临界点

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;DeepSeek MATH竞赛测试的评测定位与行业意义 DeepSeek MATH 是由深度求索&#xff08;DeepSeek&#xff09;团队构建的高难度数学推理基准&#xff0c;专为评估大语言模型在代数、微积分、组合数学、数…...

终极B站视频下载指南:BilibiliDown一键解锁高清视频下载

终极B站视频下载指南&#xff1a;BilibiliDown一键解锁高清视频下载 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader &#x1f633; 项目地址: https://gitcode.com/gh_mirrors…...

5分钟快速上手:LuckyLilliaBot QQ机器人完整部署指南

5分钟快速上手&#xff1a;LuckyLilliaBot QQ机器人完整部署指南 【免费下载链接】LuckyLilliaBot 支持 OneBot 11、Satori 和 Milky 协议 项目地址: https://gitcode.com/gh_mirrors/li/LuckyLilliaBot 你是否正在寻找一款简单易用、功能强大的QQ机器人框架&#xff1f…...

AI应用网关ai-proxy:统一管理多模型API调用,实现路由、缓存与限流

1. 项目概述&#xff1a;一个为AI应用量身打造的智能代理网关如果你正在开发或部署基于大语言模型&#xff08;LLM&#xff09;的应用&#xff0c;比如一个聊天机器人、一个代码助手&#xff0c;或者一个内容生成工具&#xff0c;那么你大概率会遇到一个头疼的问题&#xff1a;…...