前序+后序+层次

##前序
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#!'
        return str(root.val)+'!'+self.Serialize(root.left)+self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        new_s=s.split('!')
        new_s.pop(-1)
        def deserialize():
            val=new_s.pop(0)
            if val=='#':
                return None
            node=TreeNode(int(val))
            node.left=deserialize()
            node.right=deserialize()
            return node
        return deserialize()

##后序
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#!'
        return self.Serialize(root.left)+self.Serialize(root.right)+str(root.val)+'!'
    def Deserialize(self, s):
        # write code here
        new_s=s.split('!')
        new_s.pop(-1)
        def deserialize():
            val=new_s.pop(-1)
            if val=='#':
                return None
            node=TreeNode(int(val))
            node.right=deserialize()
            node.left=deserialize()
            return node
        return deserialize()

##层次
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#!'
        lst=[str(root.val)]
        queue=[root]
        while queue:
            node=queue.pop(0)
            if node.left:
                queue.append(node.left)
                lst.append(str(node.left.val))
            else:
                lst.append('#')
            if node.right:
                queue.append(node.right)
                lst.append(str(node.right.val))
            else:
                lst.append('#')
        return '!'.join(lst)
    def Deserialize(self, s):
        # write code here
        new_s=s.split('!')
        new_s.pop(-1)
        if new_s[0]=="#":
            return None
        root=TreeNode(int(new_s[0]))
        queue=[root]
        index=1
        while queue:
            val=queue.pop(0)
            if val!=None:
                val.left=(TreeNode(int(new_s[index])) if new_s[index]!='#' else None)
                queue.append(val.left)
                index+=1
                if index>=len(new_s):
                    return root
                val.right=(TreeNode(int(new_s[index])) if new_s[index]!='#' else None)
                queue.append(val.right)
                index+=1
                if index>=len(new_s):
                    return root