二叉树序列化与反序列化相关题目（Leetcode题解-Python语言）

297. 二叉树的序列化与反序列化（剑指 Offer 37. 序列化二叉树）（剑指 Offer II 048. 序列化与反序列化二叉树）

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        return str(root.val) + ',' + str(self.serialize(root.left)) + ',' + str(self.serialize(root.right))
        
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        
        def dfs(dataList):
            node = dataList.pop(0)
            if node == '':
                return
            root = TreeNode(int(node))
            root.left = dfs(dataList)
            root.right = dfs(dataList)
            return root

        dataList = data.split(',')
        return dfs(dataList)

序列化的思路就是前序遍历，将各个节点值之间通过 ‘,’ 连接起来；反序列化时，首先根据 ‘,’ 进行分隔，得到的列表就是各个节点的值（字符串），然后进行深度遍历dfs，对每个节点进行树节点构建，左右子树则是递归。

449. 序列化和反序列化二叉搜索树

由于二叉搜素树也是二叉树，所以可以使用上一题的题解。官方题解给出了优化，但是不太好理解，暂时不掌握。

428. 序列化和反序列化 N 叉树

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        if not root:
            return ''
        data = ''
        data += str(root.val) + ',' + str(len(root.children))
        for child in root.children:
            data += ',' + self.serialize(child)
        return data
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        if not data:
            return None

        def dfs(dataList) -> 'Node':
            node = dataList.pop(0)
            if node == '':
                return
            root = Node(int(node))
            root.children = []
            size = int(dataList.pop(0))
            for _ in range(size):
                root.children.append(dfs(dataList))
            return root

        dataList = data.split(',')
        return dfs(dataList)

同样的思路，只不过序列化时的前序遍历要用 N 叉树的方法，而反序列化时的 dfs 也是要改为 N 叉树的写法，其余都一样。