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.

思路

利用先序遍历和中序遍历来重建树。因为BST自带中序遍历，所以我们只需要生成一个先序遍历的字符串，传给下一个函数即可。

先根序遍历是先访问根，再递归访问左右子节点。所以先根序遍历的第一项一定是根节点。我们又可以知道BST的中根序遍历的情况，于是我们就知道了中根序遍历当中，根节点左边的部分是左子树，右边的部分是右子树，就又可以递归地重建树结构了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 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
        """
        return " ".join(str(i) for i in self.preorder(root))
        
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        prenodes = []
        if (data):
            prenodes = map(int, data.split())
        innodes = sorted(prenodes)
        self.length = len(prenodes)
        return self.reconstruct(prenodes, innodes)
        
    def preorder(self, root):
        res = []
        if (root):
            res.append(root.val)
            for i in self.preorder(root.left):
                res.append(i)
            for i in self.preorder(root.right):
                res.append(i)
        
        return res
        
    def reconstruct(self, prenodes, innodes):
        #print prenodes, innodes, 
        if (prenodes):
            root = prenodes[0]
            div = 0
            for i, node in enumerate(innodes):
                if (root == node):
                    div = i
            #print div
            cur = TreeNode(root)
            cur.left = self.reconstruct(prenodes[1:div+1], innodes[:div])
            cur.right = self.reconstruct(prenodes[div+1:], innodes[div+1:])
            
        else:
            cur = None
        
        return cur
        
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))