序列化二叉树

题目描述

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

思路

二叉树的序列化就是采用前序遍历二叉树输出节点，再碰到左子节点或者右子节点为None的时候输出一个特殊字符”#”。对于反序列化，就是针对输入的一个序列构建一棵二叉树，我们可以设置一个指针先指向序列的最开始，然后把指针指向位置的数字转化为二叉树的结点，后移一个数字，继续转化为左子树和右子树。
序列化：比较简单，直接用递归的办法前序遍历二叉树，其中碰到空就加个#。
反序列化：这里也是在别人的GitHub上借鉴的灵感。这里引入了一个全局的变量flag，通过flag来控制序列化后的索引。这样在递归的时候可以一直把序列化结果S不加改变的放入递归函数中。递归结束的出口是当判断到#的时候，这说明到达了底部，需要返回上一级。依次递归的构建二叉树。

代码

class Solution:
    flag = -1
    def Serialize(self, root):
        # write code here
        if root == None:
            return '#'
        return str(root.val)+','+self.Serialize(root.left)+','+self.Serialize(root.right)
    def Deserialize(self, s):
        self.flag += 1
        l = s.split(',') #这里的l每次都是一样的，可以看成全局的。
        # flag每次加1，从0开始，不能超过字符串长度，否则返回None
        if self.flag >= len(s):
            return None
        root = None
        # 新建一个树对象来反序列化字符串
        if l[self.flag] != '#':
            # 往树中存值,递归输入s没问题，因为l[self.flag]是不断往后取值的
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s) #先构建左子树，发现#时回溯到上一层，开始构建右子树，也就是下一行代码。
            root.right = self.Deserialize(s)
        return root