题目描述：
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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
题目大意：
序列化是将数据结构或者对象转换成比特序列的过程，以便将其存入文件或者内存缓冲区，或者通过网络连接进行传输，以后在本机或者其他电脑环境重建。
设计一个算法序列化、反序列化一棵二叉树。对于算法的序列化/反序列化的实现方式没有限制。你只需要能够确保二叉树可以序列化成一个字符串，并且可以反序列化成原始树结构即可。
例如，你可以将题目描述中的例子序列化为："[1,2,3,null,null,4,5]"，与LeetCode OJ序列化一棵二叉树的方式相同。你不一定非要遵从这种格式，请勇于创新，并想出不同的方法来。
注意：不要使用类成员/全局/静态变量来存储状态。你的序列化与反序列化算法应当是无状态的。
解题思路：
解法I：二叉树的先序遍历，参考链接：https://leetcode.com/discuss/66147/recursive-preorder-python-and-c-o-n
Python代码：
class Codec:
def serialize(self, root):
def doit(node):
if node:
vals.append(str(node.val))
doit(node.left)
doit(node.right)
else:
vals.append('#')
vals = []
doit(root)
return ' '.join(vals)
def deserialize(self, data):
def doit():
val = next(vals)
if val == '#':
return None
node = TreeNode(int(val))
node.left = doit()
node.right = doit()
return node
vals = iter(data.split())
return doit()
解法II：二叉树的层次遍历
序列化方式1（LeetCode OJ）：
Python代码：
# 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 not root:
return '[]'
res = [root.val]
q = collections.deque([root])
while q:
front = q.popleft()
if front.left:
q.append(front.left)
if front.right:
q.append(front.right)
res.append(front.left.val if front.left else 'null')
res.append(front.right.val if front.right else 'null')
while res and res[-1] == 'null':
res.pop()
return '[' + ','.join(map(str, res)) + ']'
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if data == '[]':
return None
nodes = collections.deque([[TreeNode(o), None][o == 'null']
for o in data[1:-1].split(',')])
q = collections.deque([nodes.popleft()]) if nodes else None
root = q[0] if q else None
while q:
parent = q.popleft()
left = nodes.popleft() if nodes else None
right = nodes.popleft() if nodes else None
parent.left, parent.right = left, right
if left:
q.append(left)
if right:
q.append(right)
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
序列化方式2（使用字典 + json）：
运行结果：
[]
null
Empty tree. The root is a reference to NULL (C/C++), null (Java/C#/Javascript), None (Python), or nil (Ruby).
[1,2,3]
{"r": {"v": 3}, "l": {"v": 2}, "v": 1}
1
/ \
2 3
[1,null,2,3]
{"r": {"l": {"v": 3}, "v": 2}, "v": 1}
1
\
2
/
3
[5,4,7,3,null,2,null,-1,null,9]
{"r": {"l": {"l": {"v": 9}, "v": 2}, "v": 7}, "l": {"l": {"l": {"v": -1}, "v": 3}, "v": 4}, "v": 5}
5
/ \
4 7
/ /
3 2
/ /
-1 9
Python代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import json
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return 'null'
nodes = collections.deque([root])
maps = collections.deque([{'v' : root.val}])
tree = maps[0]
while nodes:
frontNode = nodes.popleft()
frontMap = maps.popleft()
if frontNode.left:
frontMap['l'] = {'v' : frontNode.left.val}
nodes.append(frontNode.left)
maps.append(frontMap['l'])
if frontNode.right:
frontMap['r'] = {'v' : frontNode.right.val}
nodes.append(frontNode.right)
maps.append(frontMap['r'])
return json.dumps(tree)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
tree = json.loads(data)
if not tree:
return None
root = TreeNode(tree['v'])
maps = collections.deque([tree])
nodes = collections.deque([root])
while nodes:
frontNode = nodes.popleft()
frontMap = maps.popleft()
left, right = frontMap.get('l'), frontMap.get('r')
if left:
frontNode.left = TreeNode(left['v'])
maps.append(left)
nodes.append(frontNode.left)
if right:
frontNode.right = TreeNode(right['v'])
maps.append(right)
nodes.append(frontNode.right)
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
使用json + tuple也可以，参考下面这段简洁的代码，作者：StefanPochmann
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import json
class Codec:
def serialize(self, root):
def tuplify(root):
return root and (root.val, tuplify(root.left), tuplify(root.right))
return json.dumps(tuplify(root))
def deserialize(self, data):
def detuplify(t):
if t:
root = TreeNode(t[0])
root.left = detuplify(t[1])
root.right = detuplify(t[2])
return root
return detuplify(json.loads(data))
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
本文链接：http://bookshadow.com/weblog/2015/10/26/leetcode-serialize-and-deserialize-binary-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
