-
Notifications
You must be signed in to change notification settings - Fork 0
/
297-serialize-and-deserialize-binary-tree.py
61 lines (45 loc) · 1.57 KB
/
297-serialize-and-deserialize-binary-tree.py
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
# 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
"""
# recursive func to preorder traverse the tree
def searchSubtree(root):
# mark empty children with a # token
if not root:
preorder.append("#")
# otherwise append value and recurse
else:
preorder.append(str(root.val))
searchSubtree(root.left)
searchSubtree(root.right)
preorder = []
searchSubtree(root)
out = ','.join(preorder)
return out
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def buildSubtree(index):
if index >= len(preorder) or preorder[index] == "#":
return index+1, None
node = TreeNode(int(preorder[index]))
next_i, node.left = buildSubtree(index+1)
next_i, node.right = buildSubtree(next_i)
return next_i, node
preorder = data.split(',')
_, root = buildSubtree(0)
return root
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))