'''
Description: 
Autor: Au3C2
Date: 2021-03-25 20:34:52
LastEditors: Au3C2
LastEditTime: 2021-03-25 20:35:15
'''
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return
        queue = collections.deque()
        queue.append(root)
        res = []
        while queue:
            size = len(queue)
            # level = list()
            for _ in range(size):
                cur = queue.popleft()
                if not cur:
                    continue
                res.append(cur.val)
                if not cur.left and cur.val != None:
                    cur.left = TreeNode(None)
                if not cur.right and cur.val != None:
                    cur.right = TreeNode(None)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        while res[-1] == None:
            res.pop()
        return res

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data: return
        n = len(data)
        queue = list()
        queue.append(TreeNode(data[0]))
        res = queue[0]
        if n == 1: return res
        i = 1
        while queue:
            size = len(queue)
            level = list()
            for _ in range(size):
                cur = queue.pop(0)
                if data[i] != None:
                    t = TreeNode(data[i])
                    cur.left = t
                    level.append(t)
                i += 1
                if i == n:
                    return res
                if data[i] != None:
                    t = TreeNode(data[i])
                    cur.right = t
                    level.append(t)
                i += 1
                if i == n:
                    return res
            queue = level
        return res

# 树，困难
# https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/