问题描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

image.png

解题思路：BFS遍历，使用双端队列

1 序列化 将一个根节点添加进队列，然后遍历该节点的左子树和右子树，若不为空，添加其值到res，将其加入队列。否则添加'null'到res。直到队列为空。
2 反序列化。 遍历字符串，如果字符不为‘null'，则将其加进树中。

树的定义

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

实现

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        
        if not root: return ''

        from collections import deque #双端队列
        q = deque([root])
        ans = []
        while q:
            d = q.popleft()
            ans.append(str(d.val) if d else 'null')
            if d: q.extend([d.left, d.right])  #extend添加多个值
        return ','.join(ans)

        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return
        seq = data.split(',')#按照，进行分割字符串
        root = TreeNode(int(seq[0]))
        dq = deque([root])
        i = 0
        while dq:
            node = dq.popleft()
            i += 1
            if seq[i] != 'null': #左子树
                node.left = TreeNode(int(seq[i]))
                dq.append(node.left)
            i += 1
            if seq[i] != 'null':#右子树
                node.right = TreeNode(int(seq[i]))
                dq.append(node.right)
        return root

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree