序列化和反序列化一个二叉树，是很开放的一题，就是给出一个二叉树，用序列化方法生成一个字符串；然后用反序列化方法把这个字符串生成原来二叉树。这个在编程时候各个类型一般都有序列化的，用于存储。

这里面要用到python中list转化字符串方法 ','.join(list), 和字符串转换为list的方法string.split(',')。

其实可以用之前刷题的几个题目来组合，比如遍历二叉树生成中序和后序两个队列，合并为一个队列，作为序列化方法；然后有一题是按照中序和后序队列生成二叉树，就可以作为反序列化的方法使用。当然，这样会有很多冗余数据。

其实这个题目比较麻烦的地方就是优化，实现倒是很不难。

我这边用了序列化层级遍历，就是从根节点到叶子节点一层层按照从左到用遍历，如果某个节点的左或者右子节点为空，用#号代替；最后叶子节点下面会都是”#“号，这里做了个判断，如果某层都是#号，视作为空，结束遍历。

反序列化采用对应的方法，这里不多说，看代码即可。

#Definitionforabinarytreenode.#classTreeNode(object):#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassCodec:defserialize(self,root):"""Encodesatreetoasinglestring.:typeroot:TreeNode:rtype:str"""ifroot!=None:checkList=[root]else:checkList=[]AllNodeList=[]whilecheckList!=[]:nextList=[]forNodeincheckList:ifNode!='#':AllNodeList.append(str(Node.val))ifNode.left==None:nextList.append('#')else:nextList.append(Node.left)ifNode.right==None:nextList.append('#')else:nextList.append(Node.right)else:AllNodeList.append(Node)iflen(set(nextList))==1and'#'innextList:nextList=[]checkList=nextListreturn','.join(AllNodeList)defdeserialize(self,data):"""Decodesyourencodeddatatotree.:typedata:str:rtype:TreeNode"""ifdata=='':currentLevel=[]root=Noneelse:AllNodeList=data.split(",")root=TreeNode(int(AllNodeList.pop(0)))currentLevel=[root]whilecurrentLevel!=[]andAllNodeList!=[]:nextLevel=[]fornodeincurrentLevel:leftValue=AllNodeList.pop(0)ifleftValue!='#':node.left=TreeNode(int(leftValue))nextLevel.append(node.left)rightValue=AllNodeList.pop(0)ifrightValue!='#':node.right=TreeNode(int(rightValue))nextLevel.append(node.right)print([node.valfornodeinnextLevel])currentLevel=nextLevelreturnroot#YourCodecobjectwillbeinstantiatedandcalledassuch:#codec=Codec()#codec.deserialize(codec.serialize(root))