LeetCode 按层序列化&反序列化二叉树-蒲公英云

LeetCode 按层序列化&反序列化二叉树

清疚 2023-07-08 09:13 120阅读 0赞

用数组从0开始存储按层序列化二叉树的结果，则某个节点的索引为i的话，那么其左右子节点的索引分别为2i+1, 2i+2，反序列化时用得上，感觉这样更直观一些。时间复杂度一般般。
在这里插入图片描述

from collections import deque
class Codec:
    def serialize(self, root):    #序列化
        if not root:
            return '[]'
        res = ''
        q = deque([root, ])
        while q:
            node = q.popleft()
            if node:               
                res = res + str(node.val) +','
                q.append(node.left)
                q.append(node.right)
            else:            #序列化过程出现空节点时，就没有必要把空节点的左右子节点加入队列，没有意义。只对序列结果添加的=一个空节点的标志即可。
                res = res + 'None' +','
        return res[:-1]
    def deserialize(self, data):
        if data == '[]':
            return []
        data = data.split(',')
        root = TreeNode(int(data[0]))
        q = deque([root, ])
        i = 0
        while q:
            node = q.popleft()
            try:
                node.left = TreeNode(int(data[2*i+1]))
            except:
                node.left = None
            try:
                node.right = TreeNode(int(data[2*i+2]))
            except:
                node.right = None
            if node.left:   #反序列化过程遇到空节点也不加入队列，处理方式和序列化时相同
                q.append(node.left)
            if node.right:
                q.append(node.right)
            i += 1
        return root