Facebook背靠背实习挂经

依我来看，给出的应该不是一随意的乱序，而是一个BST的先根序遍历。所以还是照搬449的做法。

1. class TreeNode(object):
   
2.     def __init__(self, x):
   
3.         self.val = x
   
4.         self.left = None
   
5.         self.right = None
   
6. 
   
7. class Codec:
   
8. 
   
9.     def serialize(self, root):
   
10.         """Encodes a tree to a single string.
    
11. 
    
12.         :type root: TreeNode
    
13.         :rtype: str
    
14.         """
    
15.         R = []
    
16.         L = [root]
    
17. 
    
18.         def DFS(node):
    
19.             if node:
    
20.                 R.append(node.val)
    
21.                 DFS(node.left)
    
22.                 DFS(node.right)
    
23. 
    
24.         DFS(root)
    
25.         return R
    
26. 
    
27.     def deserialize(self, data):
    
28.         """Decodes your encoded data to tree.
    
29. 
    
30.         :type data: str
    
31.         :rtype: TreeNode
    
32.         """
    
33. 
    
34.         def BuildTree(start, end):
    
35.             if start >= end:
    
36.                 return None
    
37.             i = start + 1
    
38.             while i < end and data[i] < data[start]:
    
39.                 i += 1
    
40.             root = TreeNode(data[start])
    
41.             root.left = BuildTree(start + 1, i)
    
42.             root.right = BuildTree(i, end)
    
43.             return root
    
44. 
    
45.         return BuildTree(0, len(data))

复制代码