leetcode [449] 序列化和反序列化二叉搜索树

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

普遍使用与二叉树的层次遍历解法：

class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        if root is None: return ''
        res = ''
        queue = [root]
        while queue:
            node = queue[0]
            queue = queue[1:]
            if node is None:
                res += '#,'
                continue
            res += str(node.val) + ','
            queue.append(node.left)
            queue.append(node.right)
        return res
        

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if len(data) == 0:
            return None
        data = data.split(',')
        root = TreeNode(data[0])
        data = data[1:]
        queue = [root]
        while queue:
            node = queue[0]
            queue = queue[1:]
            if node is None: continue
            node.left = TreeNode(data[0]) if data[0] != '#' else None
            data = data[1:]
            queue.append(node.left)
            node.right = TreeNode(data[0]) if data[0] != '#' else None
            data = data[1:]
            queue.append(node.right)
        return root

为了节省空间，利用搜索树的特点，使用后续遍历，可以省去#，来自题解:

class Codec:
    def serialize(self, root):
        """
        Encodes a tree to a single string.
        """
        def postorder(root):
            return postorder(root.left) + postorder(root.right) + [root.val] if root else []
        return ' '.join(map(str, postorder(root)))

    def deserialize(self, data):
        """
        Decodes your encoded data to tree.
        """
        def helper(lower = float('-inf'), upper = float('inf')):
            if not data or data[-1] < lower or data[-1] > upper:
                return None
            
            val = data.pop()
            root = TreeNode(val)
            root.right = helper(val, upper)
            root.left = helper(lower, val)
            return root
        
        data = [int(x) for x in data.split(' ') if x]
        return helper()