[LeetCode]Serialize and Deserialize BST

题目描述:

LeetCode 449. Serialize and Deserialize BST

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

题目大意:

序列化是指将数据结构或者对象转换为比特序列,使其可以保存在文件或者内存缓冲区中,也可以通过网络链路传输给本机或者其他计算机,在之后进行重构。

设计算法序列化/反序列化一棵二叉搜索树。对序列化/反序列化算法的具体实现没有限制。你需要确保一棵二叉树可以序列化成字符串,字符串可以反序列化为原始二叉树。

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

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

解题思路:

先序遍历(Preorder Traversal)

根据二叉搜索树(BST)的性质,左孩子 < 根节点 < 右孩子,因此可以通过先序遍历的结果唯一确定一棵原始二叉树。

序列化(Serialization):

先序遍历原始二叉树,输出逗号分隔值字符串。

反序列化(Deserialization):

利用栈(Stack),节点栈nstack保存重建二叉树过程中的节点,最大值栈rstack保存当前节点的右孩子允许的最大值。

遍历序列化串,记当前数值为val,新增树节点node = TreeNode(val);记nstack的栈顶元素为ntop(nstack[-1])

若val < ntop,则val为ntop的左孩子,令ntop.left = node,并将node压入nstack;将ntop.val压入rstack

否则,val应为右孩子,但其父节点并不一定为ntop:

    记rstack的栈顶元素为rtop,当val > rtop时,执行循环:
    
        重复弹出nstack,直到ntop不是右孩子为止(nstack[-1] > nstack[-2]条件不成立)
        
        再次弹出nstack, 并弹出rstack

    上述过程执行完毕后,令ntop.right = node,并将node压入nstack

Python代码:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return ''
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        ans = str(root.val)
        if left: ans += ',' + left
        if right: ans += ',' + right
        return ans

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data: return None
        nstack, rstack = [], [0x7FFFFFFF]
        for val in map(int, data.split(',')):
            node = TreeNode(val)
            if nstack:
                if val < nstack[-1].val:
                    nstack[-1].left = node
                    rstack.append(nstack[-1].val)
                else:
                    while val > rstack[-1]:
                        while nstack[-1].val > nstack[-2].val:
                            nstack.pop()
                        rstack.pop()
                        nstack.pop()
                    nstack[-1].right = node
            nstack.append(node)
        return nstack[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

 

本文链接:http://bookshadow.com/weblog/2016/11/01/leetcode-serialize-and-deserialize-bst/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码