[剑指Offer]序列化二叉树

题目描述

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

解题思路

  1. 序列化:递归思想。使用前序遍历序列来存储,空结点使用#标注。
  2. 反序列化:递归思想。特别需要一个额外的变量来指出递归的位置,代码中将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