原题
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
样例,给出一个测试数据样例， 二叉树{3,9,20,#,#,15,7}，表示如下的树结构：
3
/ \
9 20
/ \
15 7
解题思路
- 序列化：Recursion - 先序遍历，null用#代替，上面的例子先序遍历后成为[3, 9, #, #, 20, 15, #, #, 7, #, #]
- 反序列化： 根据[3, 9, #, #, 20, 15, #, #, 7, #, #]反序列化，采用先序遍历的思想每次读取一个结点，如果读取到#，忽略。如果读取到结点数值，则插入到当前结点，然后遍历左孩子和右孩子。
- BFS，二叉树的层次遍历, 序列化为[3, 9, 20, #, #, 15, 7, #, #, #, #]
- Python中的两个内置函数 - iter() 和 next()
- iter() takes an iterable object and returns an iterator.
- Each time we call the next() method on the iterator gives us the next element.
完整代码
# 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 ''
def dfs(node):
if node:
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
else:
res.append("#")
res = []
dfs(root)
return ' '.join(res)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if len(data) == 0:
return None
def dfs():
val = next(res)
if val == '#':
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
res = iter(data.split())
return dfs()
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
