Leetcode Link: 297. 二叉树的序列化与反序列化 - 力扣（LeetCode）
题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
解法一
思路：DFS 使用任意先序、中序、后序的方式遍历二叉树，并在对应的位置将节点值添加到字符串中。（中序我还没弄会）
Attention
任何遍历方式如果不记录空节点都会导致恢复出来的树不是唯一的 而如果遍历的时候记录空节点为某个特殊的字符，就可以使得恢复出来的二叉树是唯一的。 对应的可以看看这道题：从前序与中序遍历构造二叉树
然而，在序列化的过程中，需要注意下面几点
- 要有分隔符，不然没办法区分一个两位数是属于一个节点还是属于两个节点，本题中使用
_为分隔符 - 要标记空节点，本题中使用
#标记空节点 - 个人感觉先序遍历最简单，即中左右
在反序列化的过程中，注意以下几点：
- 问题可以分解成子问题，对于每个节点，给定一个序列化的字符串，第一个值就是当前节点的值，pop出来后将剩下的部分依次送到左右子树中完成重建
- 用队列做会方便一点
- 使用队列的时候一定注意什么时候使用
q.popleft()，一个好的建议是专门使用一个变量存q.popleft()，而不是直接使用，这样避免了误操作。
为什么反序列化能够通过记录了 None 节点信息的序列唯一恢复二叉树呢？
实际上，通过反序列化得到的树，它的所有空节点，都不是创建
TreeNode的时候自动定义的那个None，而是通过判定是不是空节点的信息而返回的None，即下面的 base case
题解：
'''
Introduction:
Your Codec object will be instantiated and called as such:
ser = Codec()
deser = Codec()
ans = deser.deserialize(ser.serialize(root))
'''
class Codec:
# 先序
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def recur(node):
nonlocal res
if not node:
res = res + '#_'
return
res = res + str(node.val) + '_'
recur(node.left)
recur(node.right)
res = ''
recur(root)
return res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def recur():
nonlocal q
val = q.popleft()
# 刚开始我写成了 if q.popleft() == '#'
# 这个导致下面的用q的时候已经pop出来一个了，危险
if val == '#':
return None
cur = TreeNode(val=int(val))
cur.left = recur()
cur.right = recur()
return cur
# 构造队列
q = collections.deque()
res = data.split('_')
for c in res:
q.append(c)
# 反序列化
return recur()下面是按照后序的思路写的序列化，和先序的区别有如下几个：
- 序列化的可以直接递归完成了，需要注意分隔符的位置
- 队列要逆序一下，从左右中变成中右左
- 创建完结点之后要先制作右子树
为啥非要先弄每个节点，在弄它的左右子树呢？
我们使用的是队列。在判断base case之前都进行了
pop，我们pop出来的值如果不马上使用掉，就永远消失了。
class Codec:
# 后序
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
# 这里没有分隔符了
return '#'
left = self.serialize(root.left)
right = self.serialize(root.right)
# 分隔符全部在这，后序顺序为左右中
return left + '_' + right + '_' + str(root.val)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def recur():
nonlocal q
val = q.popleft()
if val == '#':
return None
cur = TreeNode(val=int(val))
# 注意这里，在拿到逆序的后序信息后
# 实际上是从左右中到中右左，所以先弄右子树
cur.right = recur()
cur.left = recur()
return cur
q = collections.deque()
res = data.split('_')
# 这里逆序一下，这样就是从左右中变成了中右左的顺序
for c in res[::-1]:
q.append(c)
root = recur()
return root解法二
思路：BFS todo
题解：