題目描述

請實現兩個函數，分別用來序列化和反序列化二叉樹。

解題思路

序列化二叉樹：把一棵二叉樹按照某種遍歷方式的結果以某種格式保存為字符串。需要注意的是，序列化二叉樹的過程中，如果遇到空節點，需要以某種符號（這里用#）表示。以下圖二叉樹為例，序列化二叉樹時，需要將空節點也存入字符串中。
這里寫圖片描述 ——–> 這里寫圖片描述
序列化可以基于先序/中序/后序/按層等遍歷方式進行，這里采用先序遍歷的方式實現，字符串之間用 “，”隔開。代碼如下：

def Serialize(self, root):if not root:return '#'return str(root.val) +',' + self.Serialize(root.left) +','+ self.Serialize(root.right)

反序列化二叉樹：根據某種遍歷順序得到的序列化字符串，重構二叉樹。具體思路是按前序遍歷“根左右”的順序，根節點位于其左右子節點的前面，即非空（#）的第一個節點是某子樹的根節點，左右子節點在該根節點后，以空節點#為分隔符。代碼如下：

def Deserialize(self, s):list = s.split(',')return self.deserializeTree(list)def deserializeTree(self, list):if len(list)<=0:return Noneval = list.pop(0)root = Noneif val != '#':root = TreeNode(int(val))root.left = self.deserializeTree(list)root.right = self.deserializeTree(list)return root

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[二叉树]序列化二叉树 (剑指offer61)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。