序列化和反序列化一个二叉树,是很开放的一题,就是给出一个二叉树,用序列化方法生成一个字符串;然后用反序列化方法把这个字符串生成原来二叉树。这个在编程时候各个类型一般都有序列化的,用于存储。这里面要用到python中list转化字符串方法 &
序列化和反序列化一个二叉树,是很开放的一题,就是给出一个二叉树,用序列化方法生成一个字符串;然后用反序列化方法把这个字符串生成原来二叉树。这个在编程时候各个类型一般都有序列化的,用于存储。
这里面要用到python中list转化字符串方法 ','.join(list), 和字符串转换为list的方法string.split(',')。
其实可以用之前刷题的几个题目来组合,比如遍历二叉树生成中序和后序两个队列,合并为一个队列,作为序列化方法;然后有一题是按照中序和后序队列生成二叉树,就可以作为反序列化的方法使用。当然,这样会有很多冗余数据。
其实这个题目比较麻烦的地方就是优化,实现倒是很不难。
我这边用了序列化层级遍历,就是从根节点到叶子节点一层层按照从左到用遍历,如果某个节点的左或者右子节点为空,用#号代替;最后叶子节点下面会都是”#“号,这里做了个判断,如果某层都是#号,视作为空,结束遍历。
反序列化采用对应的方法,这里不多说,看代码即可。
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if root != None: checkList = [root] else: checkList = [] AllNodeList = [] while checkList != []: nextList = [] for Node in checkList: if Node != '#': AllNodeList.append(str(Node.val)) if Node.left == None: nextList.append('#') else: nextList.append(Node.left) if Node.right == None: nextList.append('#') else: nextList.append(Node.right) else: AllNodeList.append(Node) if len(set(nextList)) == 1 and '#' in nextList: nextList = [] checkList = nextList return ','.join(AllNodeList) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data == '': currentLevel = [] root = None else: AllNodeList = data.split(",") root = TreeNode(int(AllNodeList.pop(0))) currentLevel =[root] while currentLevel != [] and AllNodeList!= []: nextLevel = [] for node in currentLevel: leftValue = AllNodeList.pop(0) if leftValue != '#': node.left = TreeNode(int(leftValue)) nextLevel.append(node.left) rightValue = AllNodeList.pop(0) if rightValue != '#': node.right = TreeNode(int(rightValue)) nextLevel.append(node.right) print([node.val for node in nextLevel]) currentLevel = nextLevel return root # Your Codec object will be instantiated and called as such:# codec = Codec()# codec.deserialize(codec.serialize(root))
--结束END--
本文标题: 刷题系列 - 序列化和反序列化一个二叉树
本文链接: https://www.lsjlt.com/news/228214.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
2024-05-24
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0