题目描述:请实现两个函数,分别用来序列化和反序列化二叉树。

Solutions

  分两个部分,序列化的部分就是采用先序遍历,空的部分用 # 代替;反序列化部分一次读取一个结点判断。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.idx = -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.idx += 1
        lis = s.split(',')
        if self.idx >= len(s):
            return None
        root = None
        if lis[self.idx] != '#':
            root = TreeNode(int(lis[self.idx]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root
# 运行时间:29ms
# 占用内存:5716k

References

  1. 062. 序列化二叉树