Python实现的序列化和反序列化二叉树算法示例
作者:hustfc 发布时间:2021-06-11 07:14:23
标签:Python,序列化,二叉树
本文实例讲述了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程序设计有所帮助。
来源:https://blog.csdn.net/weixin_36372879/article/details/84308428
0
投稿
猜你喜欢
- 通常我们做网站,设计版面布局是第一步,如何做到版面布局具有创意又美观大方呢?这就需要一定的版面处理功底。让我们先来了解一下版面布局的步骤:一
- 看看下面:<%Set objQuery = Server.CreateObject("ixss
- 本文实例讲述了PHP学习记录之面向对象(Object-oriented programming,OOP)基础。分享给大家供大家参考,具体如下
- 研究编码,得知GB2312编码与区位码的关系,尝试之后,得此程序。搜索,似乎没人写,故发此地。1.简述(1)GB2312标准的定义,其实就是
- “深入认识Python内建类型”这部分的内容会从源码角度为大家介绍Python中各种常用的内建类型。
- python中eval和int的区别是什么?下面给大家介绍一下:1.eval()函数eval(<字符串>)能够以Python表达
- 前言Django 和 DRF(django rest framawork) 的结合在 python 后台中经常出现的组合。对于异常的全局处理
- 在blueidea上看到movoin转的一个动态加载include文件代码,接着dnawo又修改了下,我用了dnawo修改后的版本,感觉挺好
- 在 ASP(VBScript 为语言)中,Asc 函数的返回值小于 0 的,可以被判断为中文字符。Asc 函数返回与字符串的第一个字母对应的
- 本文实例为大家分享了python实现人脸签到系统的具体代码,供大家参考,具体内容如下简易版人脸签到/签退系统管理员可进行录入人脸操作,以及导
- asp之家注:学习asp,无论是做企业网站还是做个人网站一般都需要用到IP地址。如留言要记录留言者IP,用户登录也经常记录登录的IP,还有站
- 在更改列顺序之前,你需要考虑是否的确需要更改表中的列顺序。SQL的核心要点是从数据存储格式获取应用。总应指定检索数据的顺序。在下面的第1条语
- 这个跟ping那个差不多,ping的那个脚本就是通过这个改了下,大体一致,不过telnet的不需要判断返回的字符串。快一些这里具体需要tel
- CSS是制作网页效果必不可少的东西,字体的颜色定义、表格的样式定义、图片的特效等等都少不了它。但在Dr
- 目录1. 递归函数与回溯深搜的基础知识2. 求子集 (LeetCode 78)3. 求子集2 (LeetCode 90)4. 组合数之和(L
- 今天交流会上,分享前端的开发经验,有一条虽然很快带过,但是我倒是印象蛮深刻的,就写点小结来分享一下吧。不知道是标准害了大家还是大家害了标准,
- 本文实例讲述了Python实现读取SQLServer数据并插入到MongoDB数据库的方法。分享给大家供大家参考,具体如下:# -*- co
- Windows中升级MySQL应采取的步骤:1. 进行升级前你应先备份当前的MySQL安装。2. 下载最新Windows版MySQL。3.
- 本文实例讲述了es6函数之严格模式用法。分享给大家供大家参考,具体如下:从es5开始,函数内部可以设定为严格模式。function doSo
- 希腊Web 设计师Christos Chiotis 发表在 CssGlobe 的一篇文章,讲述了黄金分割率在 CSS 中的应用。黄金分割率是