二叉树的序列化与反序列化

难度: 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

Submission

运行时间: 45 ms

内存: 18.2 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 not root: return '[]'
        res = []
        que = collections.deque()
        que.append(root)

        while que:
            tmp = que.popleft()
            if tmp:
                res.append(str(tmp.val))
                que.append(tmp.left)
                que.append(tmp.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 == '[null]' or data == '[]': return
        val, i = data[1:-1].split(','), 1
        root = TreeNode(int(val[0]))
        que = collections.deque()
        que.append(root)
        while que:
            tmp = que.popleft()
            if val[i] != 'null':
                tmp.left = TreeNode(int(val[i]))
                que.append(tmp.left)
            i += 1
            if val[i] != 'null':
                tmp.right = TreeNode(int(val[i]))
                que.append(tmp.right)
            i += 1
        return root
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

Explain

该题解采用层次遍历（BFS）的方式进行二叉树的序列化与反序列化。对于序列化，从根节点开始，使用队列存储每层的节点，依次将节点的值转为字符串，若节点为空则存储为'null'。结果存储为一个由逗号分隔的字符串，外围用方括号包裹。反序列化时，将字符串转换回二叉树。首先将除去方括号的字符串按逗号分隔成数组，然后使用一个队列来按层次重建树结构。每次从队列中取出一个节点作为父节点，然后读取数组中的两个值，分别设置为左右子节点，若值为'null'则对应子节点为空。这样，通过数组的顺序和队列中节点的顺序可以正确重建整个树结构。

时间复杂度: O(n)

空间复杂度: O(n)

class Codec:

    def serialize(self, root):
        \"\"\"Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        \"\"\"
        if not root: return '[]' # 空树返回空数组表示
        res = []
        que = collections.deque()
        que.append(root)

        while que:
            tmp = que.popleft()
            if tmp:
                res.append(str(tmp.val)) # 添加当前节点的值
                que.append(tmp.left) # 将左子节点加入队列
                que.append(tmp.right) # 将右子节点加入队列
            else:
                res.append('null') # 空节点添加'null'
        return '[' + ','.join(res) + ']'
        

    def deserialize(self, data):
        \"\"\"Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        \"\"\"
        if data == '[null]' or data == '[]': return # 空数据返回空树
        val, i = data[1:-1].split(','), 1 # 移除方括号并分割字符串
        root = TreeNode(int(val[0])) # 创建根节点
        que = collections.deque()
        que.append(root) # 加入队列以进行层次遍历

        while que:
            tmp = que.popleft()
            if val[i] != 'null':
                tmp.left = TreeNode(int(val[i])) # 创建左子节点
                que.append(tmp.left) # 加入队列
            i += 1
            if val[i] != 'null':
                tmp.right = TreeNode(int(val[i])) # 创建右子节点
                que.append(tmp.right) # 加入队列
            i += 1
        return root

Explore

选择层次遍历（BFS）进行序列化的主要原因是它能更直观地表示节点间的层级关系，且在反序列化时可以更容易地重建整个树结构。使用BFS序列化时，每个节点的孩子节点紧随其后，这样在反序列化过程中只需按顺序处理即可正确恢复树结构。而DFS（如前序、中序或后序）虽然也能用于序列化，但在反序列化时可能需要更多的逻辑来确定节点之间的父子关系，尤其是在树结构不完全（如缺少某些子节点）时更加复杂。

在反序列化过程中，若输入字符串格式错误或数据不完整，理想的处理方式是算法能够检测出这些错误并抛出异常或返回错误信息。例如，如果数据项数不正确或格式不符合预期（如缺少括号、逗号位置错误等），算法应该验证输入数据的有效性并在发现问题时停止处理，返回错误提示或空树。这样可以避免生成无效或错误的树结构，保证程序的健壮性和数据的准确性。

在序列化的结果中使用'null'来标记空节点是为了在反序列化时能够准确地重建整个树的结构，包括那些空缺的部分。如果省略空节点，将无法从序列化的结果中区分哪些位置应当是空节点，从而无法恢复出与原始树结构完全相同的树。使用'null'作为占位符，可以确保每个节点的位置信息被保留，包括它们是否有左右子节点的信息，这对于树的结构完整性至关重要。