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.
DFS
# 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
"""
if root is None:
return "#"
return str(root.val) + " " + self.serialize(root.left) + " " + self.serialize(root.right) def deserialize(self, data):
"""Decodes your encoded data to tree. :type data: str
:rtype: TreeNode
"""
data = data.split()
return self.deserialize_helper(data, []) def deserialize_helper(self, data, i):
if data[i[]] == "#":
return None
root = TreeNode(int(data[i[]]))
i[] +=
root.left = self.deserialize_helper(data, i)
i[] +=
root.right = self.deserialize_helper(data, i)
return root # Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
DFS 2:
# 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
"""
if root is None:
return "#"
return str(root.val) + " " + self.serialize(root.left) + " " + self.serialize(root.right) def deserialize(self, data):
"""Decodes your encoded data to tree. :type data: str
:rtype: TreeNode
"""
data = data.split()
if data[0] == '#':
return None
node = root = TreeNode(int(data[0]))
stack = [root]
i = 1
while data[i] != '#':
node.left = TreeNode(int(data[i]))
stack.append(node.left)
node = node.left
i += 1
while stack:
node = stack.pop()
i += 1
if data[i] != '#':
node.right = TreeNode(int(data[i]))
stack.append(node.right)
node = node.right
i += 1
while data[i] != '#':
node.left = TreeNode(int(data[i]))
stack.append(node.left)
node = node.left
i += 1
else:
node.right = None
return root # Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
BFS
# 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
"""
if root is None:
return ""
stack = [root]
ans = str(root.val)
while stack:
stack2 = []
for node in stack:
if node.left:
stack2.append(node.left)
ans += " "+str(node.left.val)
else:
ans += " #"
if node.right:
stack2.append(node.right)
ans += " " + str(node.right.val)
else:
ans += " #"
stack = stack2
return ans def deserialize(self, data):
"""Decodes your encoded data to tree. :type data: str
:rtype: TreeNode
"""
array = data.split()
if not array:
return None
root = TreeNode(int(array[]))
stack = [root]
i =
while stack:
stack2 = []
for node in stack:
if array[i] != '#':
node.left = TreeNode(int(array[i]))
stack2.append(node.left)
else:
node.left = None
i +=
if array[i] != '#':
node.right = TreeNode(int(array[i]))
stack2.append(node.right)
else:
node.right = None
i +=
stack = stack2
return root # Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))