二叉树序列化 反序列化

二叉树序列化

使用python 的 list comprehension

def serialize(self, root):
    """Encodes a tree to a single string.
    :type root: TreeNode
    :rtype: str
    """
    if not root:
        return
    cur = [root]
    res = []
    while cur:
        vals = [x.val if x else '#' for x in cur] # 解决当前层的编码问题 可能出现空节点
        res += vals
        cur = [c for x in cur if x for c in [x.left, x.right]] # 得到当前层的孩子，刷新cur
    return ','.join(list(map(str, res)))

去除Python特性

def serialize_(self, root): # 不使用Python的list comprehension
    if not root:
        return
    cur = [root]
    res = []
    while cur:
        for node in cur:
            if node:
                res.append(node.val)
            else:
                res.append('#')
        childs= []
        for node in cur:
            if node:
                childs += [node.left, node.right]
        cur = childs
    return ','.join(list(map(str, res)))

反序列化

确保了cur中的node都是非空的

image

从上图可以看出 编码的过程中空节点有必要留下 为了能够编码出#

解码时空节点没必要留下, cur只存放非空节点, 反而方便下一轮的链接孩子节点

def deserialize(self, data):
    """Decodes your encoded data to tree.
    :type data: str
    :rtype: TreeNode
    """
    if not data:
        return
    data = data.split(',')
    root = TreeNode(data[0])
    cur = [root]
    i = 1
    while i < len(data):
        childs = []
        for node in cur:
            if data[i] != '#': # 处理node的左孩子
                node.left = TreeNode(data[i])
                childs.append(node.left)
            i += 1
            if data[i] != '#': # 处理node的右孩子
                node.right = TreeNode(data[i])
                childs.append(node.right)
            i += 1
        cur = childs
    return root