力扣 297. 二叉树的序列化

层序遍历树

# 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
        """
        if not root: return "null"
        # 层序遍历
        ret, queue = [], [root]
        while queue:
            for _ in range(len(queue)):
                cur = queue.pop(0)
                if cur == None:
                    ret.append("null")
                    continue
                ret.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
        return " ".join(map(str, ret))


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # 层序构建树
        data = data.split(" ")
        if data[0] == "null":
            return None
        head = TreeNode(int(data[0]))
        nodes = [head]
        j = 1
        for node in nodes:
            if node != None:
                node.left = TreeNode(int(data[j])) if data[j] != "null" else None
                nodes.append(node.left)
                j += 1
                if j >= len(data):
                    return head
                node.right = TreeNode(int(data[j])) if data[j] != "null" else None
                nodes.append(node.right)
                j += 1
                if j >= len(data):
                    return head