# 请实现两个函数，分别用来序列化和反序列化二叉树
#
# 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
# 序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，
# 序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
#
# 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 就是说，任意实现一种序列化方式，然后他会用你写的序列化方式生成一个字符串，然后他会用这个字符串再去用你的反序列化方法看看能不能还原回这个字符串
class Solution:
    def __init__(self):
        self.res = [[]]
        self.root = None

    def Serialize(self, root):
        # write code here
        if not root:
            return None
        self.get_level(root,1)
        result = ''
        self.res.pop()
        for i in self.res:
            for j in i:
                result+=j
        return result

    def get_level(self,my_root,level):
        if not my_root:
            self.res[level-1].append('#!')
            return None
        self.res[level-1].append(str(my_root.val)+'!')
        if len(self.res)==level:
            self.res.append([])
        self.get_level(my_root.left,level+1)
        self.get_level(my_root.right,level+1)

    def Deserialize(self, s):
        # write code here
        if not s:
            return None
        s1 = s.split('!')
        s1.pop()#去掉末尾的空元素
        self.get_re(s1)
        return self.root

    def get_re(self, s1):

        self.root = TreeNode(int(s1.pop(0)))
        s2 = []
        s3 = []
        if len(s1)>0:
            self.root.left = None if s1[0]=='#' else TreeNode(int(s1[0]))
            s1.pop(0)
        if len(s1)>0:
            self.root.right = None if s1[0]=='#' else TreeNode(int(s1[0]))
            s1.pop(0)
        # if self.root.left:
        s2.append(self.root.left)
        # if self.root.right:
        s2.append(self.root.right)

        while len(s1)>0:
            while len(s2)>0:
                if s2[0] == None:
                    s2.pop(0)
                    continue
                if len(s1)>0:
                    s2[0].left = None if s1[0]=='#' else TreeNode(int(s1[0]))
                    s3.append(s2[0].left)
                    s1.pop(0)
                if len(s1)>0:
                    s2[0].right = None if s1[0]=='#' else TreeNode(int(s1[0]))
                    s3.append(s2[0].right)
                    s1.pop(0)
                s2.pop(0)

            while len(s3)>0:
                if s3[0] == None:
                    s3.pop(0)
                    continue
                if len(s1)>0:
                    s3[0].left = None if s1[0]=='#' else TreeNode(int(s1[0]))
                    s2.append(s3[0].left)
                    s1.pop(0)
                if len(s1)>0:
                    s3[0].right = None if s1[0]=='#' else TreeNode(int(s1[0]))
                    s2.append(s3[0].right)
                    s1.pop(0)
                s3.pop(0)
        return self.root

# 解法2：递归进行反序列化

class Solution1:
    def __init__(self):
        self.flag = -1

    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
        self.flag += 1
        l = s.split('!')

        if self.flag >= len(s):
            return None
        root = None

        if l[self.flag] != '#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root


node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node7 = TreeNode(11)

node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
node3.right = node7

my_sol = Solution()

# my_sol.Serialize(node1)
my_sol.Deserialize('5!')
print(my_sol.root)