[剑指Offer]序列化二叉树

题目描述

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

解题思路

1. 序列化：递归思想。使用前序遍历序列来存储，空结点使用#标注。
2. 反序列化：递归思想。特别需要一个额外的变量来指出递归的位置，代码中将falg放到class下指示其相对于根节点的初始值。

代码

Python(2.7.3)

# -*- 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