题目:请实现两个函数,分别用来序列化和反序列化二叉树
牛客网:链接
序列化二叉树:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是,序列化二叉树的过程中,如果遇到空节点,需要以某种符号(这里用#)表示。序列化可以基于前序/中序/后序/按层等遍历方式进行,这里采用前序遍历的方式实现,字符串之间用 “,”隔开。
反序列化二叉树:根据某种遍历顺序得到的序列化字符串,重构二叉树。具体思路是按前序遍历“根左右”的顺序,根节点位于其左右子节点的前面,即非空(#)的第一个节点是某子树的根节点,左右子节点在该根节点后,以空节点#为分隔符。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
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 None
val = list.pop(0)
# 有可能是空树
root = None
if val != '#':
root = TreeNode(int(val))
root.left = self.deserializeTree(list)
root.right = self.deserializeTree(list)
return root