61 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。例如：二叉树 [1,2,3,null,null,4,5] 可以序列化为 "1,2,3,null,null,4,5"。

解题思路

核心思想：使用前序遍历进行序列化。

Python 实现

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


def serialize(root):
    """
    序列化二叉树

    Args:
        root: 二叉树根节点

    Returns:
        str: 序列化结果
    """
    if not root:
        return ""

    result = []

    def preorder(node):
        if not node:
            result.append("null")
            return

        result.append(str(node.val))
        preorder(node.left)
        preorder(node.right)

    preorder(root)
    return ','.join(result)


def deserialize(data):
    """
    反序列化二叉树

    Args:
        data: 序列化字符串

    Returns:
        TreeNode: 二叉树根节点
    """
    if not data:
        return None

    values = data.split(',')
    index = 0

    def build():
        nonlocal index
        if index >= len(values):
            return None

        if values[index] == "null":
            index += 1
            return None

        node = TreeNode(int(values[index]))
        index += 1
        node.left = build()
        node.right = build()
        return node

    return build()


# 测试代码
if __name__ == "__main__":
    # 构建树:
    #     1
    #    / \
    #   2   3
    #      / \
    #     4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(5)

    serialized = serialize(root)
    print(f"序列化: {serialized}")

    deserialized = deserialize(serialized)
    print(f"反序列化后的序列化: {serialize(deserialized)}")

# 输出:
# 序列化: 1,2,null,null,3,4,null,null,5,null,null
# 反序列化后的序列化: 1,2,null,null,3,4,null,null,5,null,null