题目描述：
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/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
