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

这里面要用到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))