本文實(shí)例講述了Python實(shí)現(xiàn)的序列化和反序列化二叉樹算法。分享給大家供大家參考，具體如下：
題目描述
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹
序列化二叉樹
先序遍歷二叉樹
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:]結(jié)果：
root = TreeNode(11)root.left = TreeNode(2)root.right = TreeNode(3)series = Solution().Serialize(root)print(series)>>>11,2,$,$,3,$,$
反序列化
先構(gòu)建根節(jié)點(diǎn)，然后左節(jié)點(diǎn)，右節(jié)點(diǎn)，同樣是遞歸
注意由于使用的是字符串的表示形式，可以先轉(zhuǎn)化為list，
print(series.split(','))>>>['11', '2', '$', '$', '3', '$', '$']然后再處理就不需要將大于10的數(shù)字轉(zhuǎn)換過來了：
def getValue(self, s, sIndex): #處理超過10的數(shù)字，將數(shù)字字符轉(zhuǎn)變?yōu)閿?shù)字 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下面是反序列化的遞歸函數(shù)：
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 = Noneclass 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的數(shù)字，將數(shù)字字符轉(zhuǎn)變?yōu)閿?shù)字 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希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
