题目描述
请实现两个函数,分别用来序列化和反序列化二叉树
解题思路
- 序列化:递归思想。使用前序遍历序列来存储,空结点使用
#
标注。 - 反序列化:递归思想。特别需要一个额外的变量来指出递归的位置,代码中将
falg
放到class
下指示其相对于根节点的初始值。
代码
Python(2.7.3)
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# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# falg用来指示反序列化的递归位置
flag = -1
def Serialize(self, root):
# write code here
if root is None:
return '#'
return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.flag += 1
s_list = s.split(',')
if self.flag > len(s):
return None
root = None
if s_list[self.flag] != '#':
root = TreeNode(int(s_list[self.flag]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root运行时间:23ms
占用内存:5736k