刷题笔记29——（先序、层序方式）实现二叉树的序列化和反序列化_二叉树 层先序列化

文章目录

• 题目描述
• 一、先序方式
• • 1. 序列化
  • 2. 反序列化
• 二、层序方式
• • 1. 序列化
  • 2. 反序列化

题目描述

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

• 一个结构，用何种文件的形式能记录下来，记录的过程就叫序列化
• 把一个文件中的内容还原出内存中的树结构，就叫反序列化
  设计一个算法来序列化和反序列化二叉树

比如一棵树，我把它序列化为一个字符串，写到文件里，然后下次建立这棵树的时候只需要读这个文件就可以了。

一、先序方式

1. 序列化

以字符！分隔，以#表示空，如果不用这些符号，就不知道遍历的123是123还是123了
res这个字符串，加上左树得到的字符串，再加上右树得到的字符串，就是序列化得到的字符串

2. 反序列化

二、层序方式

1. 序列化

先让根结点进队列，然后看左右子树是否为空，不为空就进队列，同时累加字符串

2. 反序列化

反序列化的原则就是，怎么去序列化的就怎么去反序列化。
首先依然是对序列化字符串做以！字符的分割，待会解释为什么这里用vector而不用queue

其次，反序列化。
由于不再像先序那样递归地去完成重建了，这里要保证下标和结点的对应关系，所以vector会更方便一些