问题描述参考Offer 37. 序列化二叉树
请实现两个函数，分别用于序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化和反序列化。 这并不限制你的序列/反序列化算法执行逻辑，你只需要保证二叉树可以序列化为字符串并将字符串反序列化为原始树结构即可。
例子：
输出：根 = [1, 2, 3, null, null, 4, 5]
输入：[1,2,3,空,空,4,5]
分析问题
我们都知道，不同二叉树的前序、中序、后序或层序遍历得到的遍历结果可能是相同的，也就是说，如果我们知道遍历顺序，我们无法确定唯一的二叉树树，而题目要求序列化和反序列化是一对可逆的操作，即序列化一棵树后，我们还可以在序列化后通过反序列化恢复原来的树。 所以我们需要改进二叉树的遍历过程。 这里我们以层序遍历为例。 在遍历过程中，为了不完全表示二叉树，考虑将叶子节点下的null也记录下来。 我们看一下上面的具体实现。
序列化
我们可以利用队列来实现二叉树的层序遍历。 在层序遍历过程中，我们也会退出跨越叶子节点的空值的序列化结果。 具体算法流程如下：
如果给定的二叉树为空，则间接返回“[]”，初始化一个队列queue并退出根节点。
二叉树的层序遍历。 当队列为空时跳出。
连接结果列表，用','分隔，首尾加方括号； 并返回它。反序列化
使用队列逐层构建二叉树。 具体算法流程如下：
如果data为空，则间接返回null。 初始化列表vals（去掉第一个和最后一个括号，并用逗号分隔），指针i = 1，并将根节点root入队（值vals[0]）；
逐层构建二叉树，队列为空时跳出；
只需返回根节点root即可。
我们看一下上面代码的实现。
class Codec:
def serialize(self, root):
#如果二叉树为空，间接返回"[]"
if not root:
return "[]"
#初始化一个队列
queue = collections.deque()
#将根节点退出队列中
queue.append(root)
#后果列表
res = []
#记录null的个数，遇到非空节点就将之前的null节点退出到后果列表中
null_count=0
while queue:
node = queue.popleft()
if node:
#遇到非空节点就将之前的null节点退出到后果列表中
if null_count != 0:
res.extend(["null"] * null_count)
null_count=0
res.append(str(node.val))
#node的左、右子节点入队
queue.append(node.left)
queue.append(node.right)
else:
#记录null节点的个数
null_count=null_count+1
return '[' + ','.join(res) + ']'
def deserialize(self, data):
#如果data为"[]",代表二叉树是空，间接返回
if data == "[]":
return
#初始化
vals = data[1:-1].split(',')
i=1
#初始化根节点，并将其入队
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
if i>=len(vals):
break
node = queue.popleft()
#增加左子节点
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if i>=len(vals):
break
#增加右子节点
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root【腾讯云】轻薄2核2G4M，首年65元
阿里云限时活动- for RDS MySQL 1核2G配置1.88/月快冲
