297.二叉树的序列化与反序列化.md

297. 二叉树的序列化与反序列化

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

思路很直接，先写一个序列化函数将树按某个顺序（前、中、后、层序）遍历输出，再写一个反序列化函数用相同的遍历方法将其还原。下面尝试分别用前后序和层序，注意中序无法反序列化，因为根节点在序列的位置不确定

一、前序

注意：一般语境下，单单前序遍历结果是不能还原二叉树结构的，因为缺少空指针的信息，至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的 node 列表包含空指针的信息，所以只使用 node 列表就可以还原二叉树。

观察可知node第一个元素就是根节点（关键），即1是后面数组的根。之后2是左子树的根，再之后是null，即2的左子为空，再之后是4，即2的右子树根为4……以此类推

每次取第一个元素，之后递归数组即可

class Codec:
    str = ''
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        #遍历树
        def traval(root):	
            if root == None:
                self.str += 'null,'
                return
            self.str += str(root.val) + ','
            traval(root.left)
            traval(root.right)
        #开始遍历
        traval(root)
        return self.str[:-1]
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        nodes = data.split(',')
        #构造树
        def des(nodes):
            val  = nodes.pop(0)
            if val == 'null':
                return
            root = TreeNode(int(val))
            root.left = des(nodes)
            root.right = des(nodes)
            return root
        #开始构造
        return des(nodes)

二、后序

与前序相反，最后一个就是根节点

class Codec:
    str = ''
    def serialize(self, root):
        selfstr = ''
        def traval(root):
            if root == None:
                self.str += 'null,'
                return
            traval(root.left)
            traval(root.right)
            self.str += str(root.val) + ','
				#开始遍历
        traval(root)
        return self.str[:-1]

    def deserialize(self, data):
        nodes = data.split(',')
				#构造树
        def des(nodes):
            val = nodes.pop()
            if val == 'null':
                return
            root = TreeNode(val)
            root.right = des(nodes)
            root.left = des(nodes)
            return root
        return des(nodes)

三、层序

构造也是借鉴遍历树的思路，维护一个队列，此外设置一个游标帮助遍历序列

class Codec:
    str = ''
    def serialize(self, root):
        def traval(root):
            if not root:    
                self.str += 'null,'
                return
            q = [root]
            while q:  #队列非空时，每次遍历一层
                for i in range(len(q)):  #遍历该层
                    node = q.pop(0)   #从队列头取出结点
                    #记录数据
                    if node == None:  
                        self.str += 'null,'
                    else:
                        self.str += str(node.val) + ','
                        #该节点非空，则左右子插队尾，无论是否存在
                        q.append(node.left)
                        q.append(node.right)
        #层序遍历
        traval(root)
        return self.str[:-1]

    def deserialize(self, data):
        nodes = data.split(',')
        #构造树
        def des(data):
            if len(nodes) == 0 or nodes[0] == 'null':     #排除第一个节点为空
                return None
            i=0 #游标
            root = TreeNode(int(nodes[i]))
            q = [root]
            while q:  #队列非空时，每次遍历一层
                for _ in range(len(q)):
                    node = q.pop(0)  #取出队列头
                    #注意若i非null，则i+1和i+2位置必不为空（数字或null）
                    if nodes[i+1] != 'null':    #i+1对应node的左节点
                        left = TreeNode(int(nodes[i+1]))
                        node.left = left
                        q.append(left)
                    if nodes[i+2] != 'null':    #i+2对应node的右节点
                        right = TreeNode(int(nodes[i+2]))
                        node.right = right
                        q.append(right)
                    i += 2	#游标记得更新
            return root

        return des(nodes)