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, [0]) def deserialize_helper(self, data, i): if data[i[0]] == "#": return None root = TreeNode(int(data[i[0]])) i[0] += 1 root.left = self.deserialize_helper(data, i) i[0] += 1 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[0])) stack = [root] i = 1 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 += 1 if array[i] != '#': node.right = TreeNode(int(array[i])) stack2.append(node.right) else: node.right = None i += 1 stack = stack2 return root # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))
本文转自张昺华-sky博客园博客，原文链接：http://www.cnblogs.com/bonelee/p/6242763.html
，如需转载请自行联系原作者
