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

二叉树的序列化是指将二叉树转换为一个字符串，以便存储或传输。二叉树的反序列化是指将序列化后的字符串转换为原始二叉树。

对于二叉树的序列化，可以采用前序遍历或层序遍历的方式。以下是使用前序遍历实现二叉树的序列化：

1. 将根节点的值转换为字符串，并将其添加到序列化字符串中。
2. 递归地对左子树进行序列化，将其返回的字符串添加到序列化字符串中。
3. 递归地对右子树进行序列化，将其返回的字符串添加到序列化字符串中。

以下是使用前序遍历实现二叉树的反序列化：

1. 将序列化字符串按照逗号分隔符进行拆分，得到一个字符串数组。
2. 从字符串数组中取出第一个元素作为根节点的值，并将其从数组中删除。
3. 创建一个新的节点，并将其值设置为根节点的值。
4. 递归地对左子树进行反序列化，将其返回的节点设置为新节点的左子节点。
5. 递归地对右子树进行反序列化，将其返回的节点设置为新节点的右子节点。
6. 返回新节点。

以下是使用 Python 实现二叉树的序列化和反序列化：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root: TreeNode) -> str:
        if not root:
            return ""
        res = str(root.val)
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        if left:
            res += "," + left
        if right:
            res += "," + right
        return res

    def deserialize(self, data: str) -> TreeNode:
        if not data:
            return None
        nodes = data.split(",")
        return self.buildTree(nodes)

    def buildTree(self, nodes):
        if not nodes:
            return None
        val = int(nodes.pop(0))
        root = TreeNode(val)
        root.left = self.buildTree(nodes)
        root.right = self.buildTree(nodes)
        return root

使用前序遍历序列化二叉树，例如：

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

codec = Codec()
serialized = codec.serialize(root)
print(serialized)  # "1,2,,3,,4,,5,"

使用前序遍历反序列化二叉树，例如：

deserialized = codec.deserialize(serialized)
print(deserialized.val)  # 1
print(deserialized.left.val)  # 2
print(deserialized.right.val)  # 3
print(deserialized.right.left.val)  # 4
print(deserialized.right.right.val)  # 5