python实现层次遍历二叉树（Python实现的序列化和反序列化二叉树算法示例）

python实现层次遍历二叉树

Python实现的序列化和反序列化二叉树算法示例

本文实例讲述了Python实现的序列化和反序列化二叉树算法。分享给大家供大家参考，具体如下：

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

序列化二叉树

先序遍历二叉树

?

1 2 3 4 5 6 7 8 9 10 11

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:]

结果：

?

1 2 3 4 5 6

root = TreeNode(11) root.left = TreeNode(2) root.right = TreeNode(3) series = Solution().Serialize(root) print(series) >>>11,2,$,$,3,$,$

反序列化

先构建根节点，然后左节点，右节点，同样是递归

注意由于使用的是字符串的表示形式，可以先转化为list，

?

1 2	print(series.split(',')) >>>['11', '2', '$', '$', '3', '$', '$']

然后再处理就不需要将大于10的数字转换过来了：

?

1 2 3 4 5 6

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

下面是反序列化的递归函数：

?

1 2 3 4 5 6 7 8 9 10 11 12 13

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

完整解法

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

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