-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy path1.py
More file actions
84 lines (65 loc) · 2.17 KB
/
Copy path1.py
File metadata and controls
84 lines (65 loc) · 2.17 KB
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
"""
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'
"""
class Node:
def __init__(self, val, left=None, right=None):
self.value = val
self.left = left
self.right = right
class Tree:
def __init__(self):
self.root = None
def addNode(self, node, value):
if node == None:
self.root = Node(value)
else:
if value < node.value:
if node.left == None:
node.left = Node(value)
else:
self.addNode(node.left, value)
else:
if node.right == None:
node.right = Node(value)
else:
self.addNode(node.right, value)
def serialize(node):
serialize_string = []
def process(node):
if not node:
serialize_string.append("*")
else:
serialize_string.append(str(node.value))
process(node.left)
process(node.right)
process(node)
return ','.join(serialize_string)
def deserialize(string):
values = iter(string.split(","))
def process():
value = next(values)
if value == "*":
return None
node = Node(int(value))
node.left = process()
node.right = process()
return node
return process()
if __name__ == "__main__":
numbers = [int(i.strip()) for i in input("Enter the numbers seperated by commas: ").split(",")]
tree = Tree()
for i in numbers:
tree.addNode(tree.root, i)
serializer = serialize(tree.root)
new_serializer = serialize(deserialize(serializer))
assert serializer == new_serializer