449. Serialize and Deserialize BST - cocoder39/coco39_LC GitHub Wiki

449. Serialize and Deserialize BST

One option is leveraging 297. Serialize and Deserialize Binary Tree. However, it requires additional space for null delimiter. Solution below leverage property of BST to reduce the space usage

class Codec:

    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        data = []
        self.serializeHelper(root, data)
        return ','.join(data)
    
    def serializeHelper(self, cur: TreeNode, data: list) -> None:
        if cur:
            data.append(str(cur.val))
            self.serializeHelper(cur.left, data)
            self.serializeHelper(cur.right, data)

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if not data:
            return None
        
        queue = collections.deque(data.split(','))
        return self.deserializeHelper(queue, -float("inf"), float("inf"))
        
    def deserializeHelper(self, queue: list, minVal: int, maxVal: int) -> TreeNode:
        if queue and minVal < int(queue[0]) < maxVal:
            val = int(queue.popleft())
            node = TreeNode(val)
            node.left = self.deserializeHelper(queue, minVal, val)
            node.right = self.deserializeHelper(queue, val, maxVal)
            return node