原題
設(shè)計一個算法逛万，并編寫代碼來序列化和反序列化二叉樹捻激。將樹寫入一個文件被稱為“序列化”蛾娶，讀取文件后重建同樣的二叉樹被稱為“反序列化”括勺。
如何反序列化或序列化二叉樹是沒有限制的缆八，你只需要確保可以將二叉樹序列化為一個字符串疾捍，并且可以將字符串反序列化為原來的樹結(jié)構(gòu)奈辰。
樣例,給出一個測試數(shù)據(jù)樣例， 二叉樹{3,9,20,#,#,15,7}乱豆，表示如下的樹結(jié)構(gòu)：
3
/ \
9 20
/ \
15 7
解題思路
- 序列化：Recursion - 先序遍歷奖恰，null用#代替，上面的例子先序遍歷后成為[3, 9, #, #, 20, 15, #, #, 7, #, #]
- 反序列化： 根據(jù)[3, 9, #, #, 20, 15, #, #, 7, #, #]反序列化，采用先序遍歷的思想每次讀取一個結(jié)點瑟啃，如果讀取到#趾徽，忽略。如果讀取到結(jié)點數(shù)值翰守，則插入到當前結(jié)點孵奶，然后遍歷左孩子和右孩子。
- BFS蜡峰，二叉樹的層次遍歷, 序列化為[3, 9, 20, #, #, 15, 7, #, #, #, #]
- Python中的兩個內(nèi)置函數(shù) - 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))
