Python实现的序列化和反序列化二叉树算法示例
- 更新时间：2022-10-20 10:05:20
- 编辑：厉嘉致
本文实例讲述了Python实现的序列化和反序列化二叉树算法。分享给大家供大家参考，具体如下：
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
序列化二叉树
先序遍历二叉树
def recursionSerialize(self, root):
series = ''
if root == None:
series += ',$'
else:
series += (',' + str(root.val))
series += self.recursionSerialize(root.left)
series += self.recursionSerialize(root.right)
return series
def Serialize(self, root):
return self.recursionSerialize(root)[1:]
结果：
root = TreeNode(11) root.left = TreeNode(2) root.right = TreeNode(3) series = Solution().Serialize(root) print(series) >>>11,2,$,$,3,$,$
反序列化
先构建根节点，然后左节点，右节点，同样是递归
注意由于使用的是字符串的表示形式，可以先转化为list，
print(series.split(','))
>>>['11', '2', '$', '$', '3', '$', '$']
然后再处理就不需要将大于10的数字转换过来了：
def getValue(self, s, sIndex): #处理超过10的数字，将数字字符转变为数字
val = 0
while ord(s[sIndex]) <= ord('9') and ord(s[sIndex]) >= ord('0'):
val = val * 10 + int(s[sIndex])
sIndex += 1
return val, sIndex - 1
下面是反序列化的递归函数：
def Deserialize(self, s):
if self.sIndex < len(s):
if s[self.sIndex] == ',':
self.sIndex += 1
if s[self.sIndex] == '$':
return None
val, self.sIndex = self.getValue(s, self.sIndex)
treeNode = TreeNode(val)
self.sIndex += 1
treeNode.left = self.Deserialize(s)
self.sIndex += 1
treeNode.right = self.Deserialize(s)
return treeNode
完整解法
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.sIndex = 0
def recursionSerialize(self, root):
series = ''
if root == None:
series += ',$'
else:
series += (',' + str(root.val))
series += self.recursionSerialize(root.left)
series += self.recursionSerialize(root.right)
return series
def Serialize(self, root):
return self.recursionSerialize(root)[1:]
def getValue(self, s, sIndex): #处理超过10的数字，将数字字符转变为数字
val = 0
while ord(s[sIndex]) <= ord('9') and ord(s[sIndex]) >= ord('0'):
val = val * 10 + int(s[sIndex])
sIndex += 1
return val, sIndex - 1
def Deserialize(self, s):
if self.sIndex < len(s):
if s[self.sIndex] == ',':
self.sIndex += 1
if s[self.sIndex] == '$':
return None
val, self.sIndex = self.getValue(s, self.sIndex)
treeNode = TreeNode(val)
self.sIndex += 1
treeNode.left = self.Deserialize(s)
self.sIndex += 1
treeNode.right = self.Deserialize(s)
return treeNode
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
相关教程
-
Python实现去除图片中指定颜色的像素功能示例
为网友们分享了关于Python的教程，这篇文章主要介绍了Python实现去除图片中指定颜色的像素功能,结合具体实例形式分析了Python基于pil与cv2模块的图形载入、运算、转换等相关操作技巧,需要的朋友可以参考下
发布时间：2022-09-07
-
Python通过pip安装Django步骤代码
这篇文章主要介绍了Python 通过pip安装Django详细介绍的相关资料,需要的朋友可以参考下
发布时间：2020-01-25
-
汇总python入门书籍
适合python初学者的书籍有《Python学习手册：第3版》、《Python编程 从入门到实战》、《“笨办法”学Python（第3版）》等，非常适合python零基础小白学习。
发布时间：2020-02-01
-
python3 实现的对象与json相互转换的方法及代码
这篇文章主要介绍了python3 实现的对象与json相互转换操作,结合实例形式分析了Python3使用json模块针对json格式数据转换操作的相关实现技巧,需要的朋友可以参考下
发布时间：2020-02-16
-
Python中职责链模式原理与用法详解
这篇文章主要介绍了Python设计模式之职责链模式,结合具体实例形式分析了Python责任链模式的概念、原理、定义与使用方法,需要的朋友可以参考下
发布时间：2019-11-22
-
python input自动换行继续输入详解
在本篇文章中小编给大家分享了关于python input自动换行继续输入的相关知识点内容，有兴趣的朋友们可以参考学习下。
发布时间：2019-06-27
-
介绍python中数组和矩阵乘法及使用示例代码
这篇文章主要介绍了python中数组和矩阵乘法及使用总结，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
发布时间：2020-03-16
-
Python入门的知识点总结
Python被誉为全世界高效的编程语言，同时也被称作是“胶水语言”，那它为何能如此受欢迎，下面我们就来说说Python入门学习的必备11个知识点，也就是它为何能够如此受欢迎的原因，本文主要
发布时间：2020-05-19
-
Python通过URL打开图片的具体步骤
这篇文章主要介绍了Python 通过URL打开图片实例详解的相关资料,需要的朋友可以参考下
发布时间：2020-06-15
