每日一道Leetcode剑指Offer37.序列化二叉树【层次遍历】

# 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
"""
# 序列化后的形式：[1,2,3,null,null,4,5]
# 使用层次遍历
if not root:
# 如果树为空，序列化为空列表
return "[]"
queue = collections.deque()
queue.append(root)
res = []
while queue:
node = queue.popleft()
if node:# node不为空res.append(str(node.val))queue.append(node.left)queue.append(node.right)
else:# node为空res.append("null")
return '['+ ','.join(res)+']'

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
# 先判断是否为空的[]字符串,是则表示空树
if data == "[]":
return
# 去掉头尾[]，并且按照逗号分开
res = data[1:-1].split(',')
# i 从 root 节点之后一个节点开始
i = 1
# 先定义树的根节点
root = TreeNode(int(res[0]))
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if res[i]!="null":node.left = TreeNode(int(res[i]))queue.append(node.left)
i+=1
# 因为左右子树，所以判断两次
if res[i]!="null":node.right = TreeNode(int(res[i]))queue.append(node.right)
i += 1
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))