449 Serialize And Deserialize Bst
449 Serialize And Deserialize Bst
Serialize and Deserialize BST 
Serialization is 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 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.
Example 1:
1
2
3
**Input:** root = [2,1,3]
**Output:** [2,1,3]
Example 2:
1
2
3
**Input:** root = []
**Output:** []
Constraints:
1
2
3
The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is **guaranteed** to be a binary search tree.
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
#l = 2*i + 1
#r = 2*i + 2
def __init__(self):
self.inord = ""
self.preord = ""
def preorder(self, root: [TreeNode]) -> str:
if root != None and root.left == None and root.right == None:
return str(root.val)
if root == None:
return ""
m = str(root.val)
l = self.preorder(root.left)
r = self.preorder(root.right)
return ",".join(filter(None,[m,l,r]))
def inorder(self, root: [TreeNode]) -> str:
if root != None and root.left == None and root.right == None:
return str(root.val)
if root == None:
return ""
l = self.inorder(root.left)
m = str(root.val)
r = self.inorder(root.right)
return ",".join(filter(None,[l,m,r]))
def serialize(self, root: Optional[TreeNode]) -> str:
"""Encodes a tree to a single string.
"""
self.inord= self.inorder(root)
self.preord = self.preorder(root)
return self.inord + "#" + self.preord
def deserialize(self, data: str, index : int = 0) -> Optional[TreeNode]:
"""Decodes your encoded data to tree.
"""
#print(data)
arr = data.split("#")
inorder = arr[0]
preorder = arr[1]
return self.build_tree(inorder, preorder)
def build_tree(self, inorder: str, preorder: str) -> TreeNode:
if len(inorder) == 0 and len(preorder) == 0:
return None
inord = inorder.split(',')
preord = preorder.split(',')
root = TreeNode(preord[0])
left_inorder = filter(lambda a: int(a) < int(preord[0]), inord)
right_inorder = filter(lambda a: int(a) > int(preord[0]), inord)
left_preorder = filter(lambda a: int(a) < int(preord[0]), preord)
right_preorder = filter(lambda a: int(a) > int(preord[0]), preord)
#print(left_inorder, right_inorder, left_preorder, right_preorder)
root.left = self.build_tree(",".join(filter(None,left_inorder)), ",".join(filter(None, left_preorder)))
root.right = self.build_tree(",".join(filter(None, right_inorder)), ",".join(filter(None, right_preorder)))
return root
# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans
This post is licensed under CC BY 4.0 by the author.