【LeetCode力扣】297. 二叉树的序列化与反序列化
目录
1、题目介绍
2、解题思路
2.1、详细过程图解
2.2、代码描述
2.3、完整代码

1、题目介绍
原题链接:297. 二叉树的序列化与反序列化 - 力扣(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, 104]内 -1000 <= Node.val <= 1000
2、解题思路
二叉树序列化就是将内存中的二叉树变成硬盘中的字符串形式,并且要求每个二叉树能够对应一个唯一的字符串。
二叉树反序列化就是将这个唯一字符串在内存中还原回对应的二叉树。
2.1、详细过程图解
这里采用先序遍历完成序列化。只要理解了一种遍历的序列化,其他遍历(包括不限于中序遍历、后序遍历、层次遍历)的序列化都是依葫芦画瓢了。
先说规则:
- 通过先序遍历的顺序进行访问二叉树,假如访问到结点1,就将1写入字符串中,同理结点2就是写入2到节点中
- 如果遇到空结点则在字符串中存入一个标识符号,这里我采用井号 # 来表述空结点。
- 同时两个节点之间需要使用下划线 _ 隔开,也可以理解为表示一个结点值的结束。
序列化过程图解:
开始时字符串str为空。按照先序遍历,首先是访问结点1,所以此时字符串中存入了1和表示结点值结束的下划线 _。
str[ ]= "1_"

接着先序遍历访问到结点2,继续将2和下划线_拼接进字符串str中。
str[ ]= "1_2_"

接着先序遍历访问到空结点,此时将表示空姐点的标识符号井号#下划线_拼接进字符串str中。
str[ ]= "1_2_#_"

同理依次进行遍历
str[ ]= "1_2_#_#_"

通过依次遍历最后得到str字符串
str[ ]= "1_2_#_#_3_4_#_#_5_#_#_"
这个str字符串即为二叉树的序列化,而用字符串通过先序遍历还原回二叉树就成为反序列化。
反序列化过程图解:
str从前往后遍历,按照先序遍历【头左右】的顺序还原回二叉树。






依次遍历str最终完成还原回原二叉树。

2.2、代码描述
使用递归将二叉树按照先序遍历生成对应的序列化字符串ret。
// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null) //等于空时返回井号标识符{return "#_";}String res = root.val + "_"; //将结点值与下划线_拼接res += serialize(root.left); //将左子树返回的字符串拼接到当前的ret后res += serialize(root.right); //将右子树返回的字符串拼接到当前的ret后return ret;}
使用split方法对字符串进行拆分,拆分出来的值放入一个数组中,再用队列依次接收数组的 值。
// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] val = data.split("_"); //将data字符串按照下划线_为分隔符对字符串进行拆分Queue<String> queue = new LinkedList<>(); //队列for(int i = 0;i < val.length; i++) {queue.add(val[i]); //将拆分出来的值依次入队}return reconPreOrder(queue); //返回队列}
将得到的队列依次出队,通过递归判断是否为空标识符井号#,是则返回null,否则将值存入新开辟的头结点root中,再通过递归方式创建左子树以及右子树。最后将头结点root返回,即完成二叉树的反序列化。
public static TreeNode reconPreOrder(Queue<String> queue){String val = queue.poll(); //出队if(val.equals("#")) //等于#则返回null{return null;}TreeNode root = new TreeNode(Integer.valueOf(val)); //创建头结点存放val值root.left = reconPreOrder(queue); //从递归中获取左子树信息root.right = reconPreOrder(queue); //从递归中获取右子树信息return root; //最后返回头结点}
2.3、完整代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null){return "#_";}String res = root.val + "_";res += serialize(root.left);res += serialize(root.right);return res;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] val = data.split("_");Queue<String> queue = new LinkedList<>();for(int i = 0;i < val.length; i++){queue.add(val[i]);}return reconPreOrder(queue);}public static TreeNode reconPreOrder(Queue<String> queue){String val = queue.poll();if(val.equals("#")){return null;}TreeNode root = new TreeNode(Integer.valueOf(val));root.left = reconPreOrder(queue);root.right = reconPreOrder(queue);return root;}
}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

彩蛋:
在查看其他题解时发现了一个有趣的解题方法(请勿模仿)哈哈哈哈哈

关于二叉树遍历的精讲:
【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解_Hacynn的博客-CSDN博客
https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5502【算法与数据结构】二叉树的三种遍历代码实现(下)—— 非递归方式实现(大量图解)-CSDN博客
https://blog.csdn.net/zzzzzhxxx/article/details/133669283?spm=1001.2014.3001.5502

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!
相关文章:
【LeetCode力扣】297. 二叉树的序列化与反序列化
目录 1、题目介绍 2、解题思路 2.1、详细过程图解 2.2、代码描述 2.3、完整代码 1、题目介绍 原题链接:297. 二叉树的序列化与反序列化 - 力扣(LeetCode) 示例 1: 输入:root [1,2,3,null,null,4,5] 输出&#…...
Linux寄存器+Linux2.6内核进程调度队列+命令行参数+环境变量
目录 一、寄存器 二、Linux2.6内核进程调度队列 (一)优先级 (二)活动队列 (三)过期队列 (四)active指针和expired指针 三、命令行参数 (一)举例一 &…...
组合数(2)获取C(n,k)组合数列表的QT实现
1)工程文件 QT coreCONFIG c17 cmdline# You can make your code fail to compile if it uses deprecated APIs. # In order to do so, uncomment the following line. #DEFINES QT_DISABLE_DEPRECATED_BEFORE0x060000 # disables all the APIs deprecated before Qt 6.…...
SparkCore编程RDD
RDD概述 中文名为弹性分布式数据集,是数据处理基本单位。代表一个弹性的,不可变,可分区,里面的数据可并行计算的集合。 RDD和Hadoop MR 的区别: RDD是先明确数据处理流程,数据在行动算子执行前实际上并未…...
VBA技术资料MF69:添加和删除工作表中的分页符
我给VBA的定义:VBA是个人小型自动化处理的有效工具。利用好了,可以大大提高自己的工作效率,而且可以提高数据的准确度。我的教程一共九套,分为初级、中级、高级三大部分。是对VBA的系统讲解,从简单的入门,到…...
数字技术助力智慧公厕,让公厕变身为全新创新应用
在如今数字化的时代,数字技术的集成应用已经渗透到了生活的方方面面。其中一个令人瞩目的领域就是智慧公厕。以前只是简单的厕所,如今借助数字技术的力量,智慧公厕变得功能强大、智能高效。接下来,我们将以智慧公厕源头领航厂家广…...
electron 升级 v22 遇到问题
Electron 漏洞 https://mp.weixin.qq.com/s/5LpSJb_5uV8EIDOl3fz9Tw 由于 23以上不在支持win 7 8 8.1 所以我选择安装 v22.3.24 electron 22.3.24 node-sass 6.0.1 sass-loader 10.4.1 对应的版本 npm i node-sass6.0.1 --sass_binary_sitehttps://npm.taobao.org/mirrors…...
跟我学c++中级篇——Pimpl
一、前向声明 前向声明或者前置声明(forward declaration),这个在c中用得还是比较多的。一般的框架或者库中,经常可以看到在一个类的前面声明了一个类,类似下面这样: class useclass; class mycall{...useclass *us; };前向声明…...
[补题记录] Atcoder Beginner Contest 295(E)
URL:https://atcoder.jp/contests/abc295 目录 E Problem/题意 Thought/思路 Code/代码 E Problem/题意 给定长度为 N 的数组 A。进行如下操作: 若 Ai 0,将 Ai 等概率地变为 1 ~ M 中的任意一个数;对 A 排序; …...
解决git在window11操作很慢,占用很大cpu的问题
【git在window11操作很慢,占用很大cpu,最后也执行失败】 在谷歌输入:git very slow in window 11。通过下面链接终于找到了解决方案: https://www.reddit.com/r/vscode/comments/sulebx/slow_git_in_wsl_after_updating_to_window…...
C++智能指针(二)——weak_ptr初探
文章目录 1. shared_ptr 存在的问题2. 使用weak_ptr2.1 初始化 weak_ptr2.2 访问数据 3. 附录4. 参考文献 1. shared_ptr 存在的问题 与 shared_ptr 的引入要解决普通指针存在的一些问题一样,weak_ptr 的引入,也是因为 shared_ptr 本身在某些情况下&…...
540 - Team Queue (UVA)
题目链接如下: Online Judge 对比刘汝佳的代码,我没有用queue来排整个队伍,因为那样的话遍历整个队伍太麻烦,vector比较方便。但vector删除元素比较耗时,所以就不删了,仅仅用pivot来指代目前队伍的开始。…...
投资组合之如何估值
文章目录 如何估值一、PE估值法1、PE估值法的定义2、参考标准(1)常规标准:25倍合理市盈率。(2)同行业对比。(3)跟历史市盈率相比。 3、PE估值法的适用范围4、PE估值法的优势5、PE估值法的劣势&a…...
2024届通信工程保研经验分享(预推免入营即offer)
2024届通信工程保研经验分享(预推免入营即offer) BackGround夏令营情况:预推免情况: BackGround 本科院校:末九 专业:通信工程 rank:3/123(预推免绩点排名)࿰…...
L2-025 分而治之 - java
L2-025 分而治之 时间限制 600 ms 内存限制 64 MB 题目描述: 分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若…...
Python+高光谱数据预处理-机器学习-深度学习-图像分类-参数回归
涵盖高光谱遥感数据处理的基础、python开发基础、机器学习和应用实践。重点解释高光谱数据处理所涉及的基本概念和理论,旨在帮助学员深入理解科学原理。结合Python编程工具,专注于解决高光谱数据读取、数据预处理、高光谱数据机器学习等技术难题…...
免费 AI 编程助手 Amazon CodeWhisperer 体验
文章作者:文章作者:米菲爸爸 2022 年 6 月 23 亚马逊云科技就已经推出了 Amazon CodeWhisperer(预览版)。经过不到一年的测试和 AIGC的飓风在 2023 年 4 月 18 日实时 AI 编程助手 Amazon CodeWhisperer正式可用 Amazon CodeWhis…...
【Linux】从零开始学习Linux基本指令(一)
🚩纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:Linux入门 🔥该文章主要了解Linux操作系统下的基本指令。 目录: ⌛️指令的理解⏳目录和文件的理解⏳一些常见指令✉…...
Java GC 算法
一、概述 理解Java虚拟机垃圾回收机制的底层原理,是成为一个高级Java开发者的基本功。本文从底层的垃圾回收算法开始,着重去阐释不同垃圾回收器在算法设计和实现时的一些技术细节,去探索「why」这一部分,通过对比不同的垃圾回收算…...
vue3 v-html中使用v-viewer
安装:npm install v-viewernext 在main.js中配置 import “viewerjs/dist/viewer.css”; import Viewer from “v-viewer”; app.use(Viewer, { Options: { inline: true, //默认值:false。启用内联模式。 button: true, //在查看器的右上角显示按钮。 …...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版
1.题目描述 2.思路 当前的元素可以重复使用。 (1)确定回溯算法函数的参数和返回值(一般是void类型) (2)因为是用递归实现的,所以我们要确定终止条件 (3)单层搜索逻辑 二…...
虚幻基础:角色旋转
能帮到你的话,就给个赞吧 😘 文章目录 移动组件使用控制器所需旋转:组件 使用 控制器旋转将旋转朝向运动:组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转:必须移动才能旋转,不移动不旋转控制器…...
初探用uniapp写微信小程序遇到的问题及解决(vue3+ts)
零、关于开发思路 (一)拿到工作任务,先理清楚需求 1.逻辑部分 不放过原型里说的每一句话,有疑惑的部分该问产品/测试/之前的开发就问 2.页面部分(含国际化) 整体看过需要开发页面的原型后,分类一下哪些组件/样式可以复用,直接提取出来使用 (时间充分的前提下,不…...
Python打卡训练营学习记录Day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
