序列化与反序列化二叉树

难度: Hard

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

树中结点数在范围 [0, 10⁴] 内
-1000 <= Node.val <= 1000

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

Submission

运行时间: 124 ms

内存: 19.4 MB

# 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 root is None:
            return '[]'
        res = []
        queue = 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 = data[1:-1].split(',')
        root = TreeNode(vals[0])
        queue = deque()
        queue.append(root)
        i = 1
        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))

Explain

这个题解使用层序遍历（广度优先搜索）来序列化二叉树。通过使用队列来迭代访问每个节点，并将其值存储为字符串。对于空节点，它使用'null'来表示。反序列化过程中，同样采用层序遍历的方法。首先将字符串分割成节点数组，然后通过迭代构建每个节点的左右子节点。这种方法直观且符合大多数人对树结构的遍历习惯。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 root is None:
            return '[]'
        res = []
        queue = 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")
        # Remove unnecessary nulls from end to optimize the result
        while res[-1] == "null":
            res.pop()
        return '[' + ','.join(res) + ']'

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]':
            return
        vals = data[1:-1].split(',')
        root = TreeNode(int(vals[0]))
        queue = deque()
        queue.append(root)
        i = 1
        while i < len(vals):
            node = queue.popleft()
            if vals[i] != 'null':
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1
            if i < len(vals) and 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))

Explore

使用'null'表示空节点在反序列化时主要带来的挑战是如何正确地处理这些占位符，以还原出正确的树结构。在反序列化过程中需要正确地识别'null'值，并据此跳过为这些'null'创建子节点的步骤，同时确保序列中的下一个值用于正确的父节点。这要求在迭代过程中维护严格的索引控制，以免错位或丢失节点的正确关系。

在序列化过程中删除末尾不必要的'null'可以减少最终字符串的长度，从而节省存储空间和传输带宽。对于反序列化过程，这种优化不会带来负面影响，因为这些'null'是末尾的、不会影响已经存在的节点之间的关系。实际上，这样做简化了数据，使处理过程稍微轻松一些，因为处理器需要解析和转换的元素更少了。

在反序列化函数中，使用队列来确保按照层序顺序处理每个节点，并逐一为其分配左右子节点。通过从左到右读取值的数组，每次从队列中取出一个节点，然后分配其左子节点（如果当前值不是'null'），随后为其分配右子节点（同样检查是否为'null'）。这种方法利用队列的先进先出特性，确保每个节点的子节点按顺序正确地关联，从而在整个遍历过程中维护树结构的完整性。

处理非常大的二叉树时，性能瓶颈主要包括内存消耗和处理时间。序列化一个大树时，由于需要将所有节点（包括空节点）转换为字符串形式，并可能需要存储大量的'null'值，这将占用大量内存。同时，层序遍历需要队列来存储每层的节点，对于宽度很大的树，这可能导致内存使用急剧增加。反序列化过程同样需要较多内存来重新构建树，并且需要处理和转换大量的字符串数据，这可能导致处理速度下降，特别是在节点数目极大时。