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

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

解题思路：
二叉树搜索树的序列化就是将树用前序、后序和中序三种方法其中一种转化成序列。本题要求将二叉搜索树序列化和反序列化，那么我们在将它序列化的时候就要考虑序列化的结果可以保存二叉搜索树的结构。

首先我们采用后序遍历将二叉搜索树序列化：

 def postorder(root):
            return postorder(root.left) + postorder(root.right) + [root.val] if root else []

将返回结果处理成字符串就是最终结果，这里就不再写出了。

接下来，就是如何将后序排列的字符串“反序列化”成二叉搜索树：

def deserialize(treedata):
        def helper(low=float('-inf'), high=float('inf')):
            if not treedata or treedata[-1] < low or treedata[-1] > high:
                return None
            tmp = TreeNode(treedata.pop())
            #注意此处应先右后左
            tmp.right = helper(tmp.val, high)
            tmp.left = helper(low, tmp.val)
            return tmp
        treedata = [int(x) for x in treedata.split(' ') if x]
        return helper()

注释所说的先右后左，因为需要“反序列化”，也就是将后序反过来提取节点。
时间复杂度和空间复杂度都是O(N)