剑指Offer37-序列化二叉树

[ruotongyu (Dongle)]

剑指Offer37-序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

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

示例：

输入：root = [1,2,3,null,null,4,5]

输出：[1,2,3,null,null,4,5]

来源：力扣（LeetCode）

链接：力扣

一解

以下面的树举例：

序列化：

• 使用层序遍历进行序列化，这个算法前面已经练过很多遍

反序列化，上面例子的序列化结果为：

"1"，"2"，"3"，"null"，"nu1l"，"4"，"5"，"null"，"null"，"null"，"null"

后续操作以此类推…

# 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 ""

        queue, res = collections.deque(), []

        queue.append(root)

        while queue:

            node = queue.popleft()

            if node:

                res.append(str(node.val))

                queue.append(node.left)

                queue.append(node.right)

            else: res.append("null")

        return  ",".join(res)

        

    def deserialize(self, data):

        """Decodes your encoded data to tree.

        

        :type data: str

        :rtype: TreeNode

        """

        if data == "": return

        vals, i = data.split(','), 1

        root = TreeNode(int(vals[0]))

        queue = collections.deque()

        queue.append(root)

        while queue:

            node = queue.popleft()

            if vals[i] != "null":

                node.left = TreeNode(int(vals[i]))

                queue.append(node.left)

            i += 1

            if vals[i] != "null":

                node.right = TreeNode(int(vals[i]))

                queue.append(node.right)

            i += 1

        return root

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))