[297][困难][BFS] 二叉树的序列化与反序列化

题目描述

297. 二叉树的序列化与反序列化 剑指 Offer 37. 序列化二叉树

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

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

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解题思路

题目分为两部分, 序列化和反序列化.

序列化: BFS

序列化部分使用BFS的思路, 依次将每一层的结点, 放入到最终的结果列表中. 注意对于树中的空子节点, 也要以None的形式放入到列表中. 为了做到BFS, 使用队列存储遍历到的列表, 这样就能做到更接近根节点的层, 以及更靠左的结点会被先处理, 从而做到BFS.

需要注意的是, 对于列表尾部的空子节点(值为None), 都要从结果列表中剔除. 然后使用json进行序列化输出.

反序列化: 层序遍历

反序列化的关键在于分割结点列表, 控制每一层有多少结点. 上面序列化的方法, 可以保证除了最后一层, 下一层在列表中的元素数量, 是上一层在列表中的非None元素(非空节点, 空节点没有子节点)的两倍, 那么在确定了一层的节点数量之后num, 就可以拿接下来的2 * num个元素作为子节点, 按左右左右的顺序连接(如果有2 * num个元素的话, 如果没有, 说明上层靠后的结点子节点有为空的现象).

得到每一层结点数量的方法参考[102][中等] 二叉树的层序遍历. 层序遍历是有树然后生成列表, 现在有列表反推回树结构, 过程相反, 但在获得并控制每层结点数量的方法上是一样的.

# Definition for a binary tree node.
# 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
        """
        nodes = []
        queue = deque()
        if root:
            queue.append(root)
        while queue:
            node = queue.popleft()
            if node:
                nodes.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                nodes.append(None)

        while 1:
            if nodes and nodes[-1] is None:
                nodes.pop()
            else:
                break

        return json.dumps(nodes)


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        nodes = json.loads(data)
        n = len(nodes)
        if n == 0:
            return None

        queue = deque()
        root = TreeNode(nodes[0])
        queue.append(root)
        i = 1
        while queue:
            if i >= n:
                break
            num_cur_layer = len(queue)
            for _ in range(num_cur_layer):
                node = queue.popleft()
                if i >= n or nodes[i] is None:
                    node.left = None
                else:
                    new_node = TreeNode(nodes[i])
                    node.left = new_node
                    queue.append(new_node)
                i += 1
                if i >= n or nodes[i] is None:
                    node.right = None
                else:
                    new_node = TreeNode(nodes[i])
                    node.right = new_node
                    queue.append(new_node)
                i += 1
        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))