from pickle import NONE
import collections
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:

    """
	
	 解题思路***************************************************************************************************** 
     对二叉树进行层序遍历
     设置一个结果res=[] 保存每个节点 字符串  空节点保存为"#"
     1. 将root 添加到队列dq 
     2. 判断dq 是否为空  不为空则 
        判断左节点是否为空 为空保存到res,不为空 节点加dq队列,值存入
    反序列化: 
    
     1.   判空 如果 s 为{ } 直接返回None ,对字符串进行截取 {1,2,3,#,#,6,7}
     存入list  arr [1,2,3,#,#,6,7]
     2. arr[0] 作为根节点  设置一个指针指向 arr[1]  第一个左节点
     3. 遍历数组遇到 非# 作为  left 节点 i+1  遇到非#  作为right 节点 i+1 
     
     注意: 反序列化时候val 是整数 
     root=TreeNode(int(arr[0]))

      测试用例: 
      1. { }
      2. {5} 
      
    """
    def Serialize(self, root):
        # write code here
        
        def dfs(root):
            res=[]
            if root:
                dq=collections.deque()
                dq.append(root)
                while  dq:
                    node =dq.popleft()
                    if  node:
                        res.append(str(node.val))
                        dq.append(node.left)
                        dq.append(node.right)
                    else:
                        res.append("#")
            return res 
        res=dfs(root)
        ret ="{"+",".join(res)+"}"
        #print("ret",ret)
        return ret 

    def Deserialize(self, s):
        # write code here
        if not s or  s=="{}":
            return None
        arr=s[1:-1].split(",")
        #print("in",arr)
        root=TreeNode(int(arr[0]))
        i=1
        dq=collections.deque()
        dq.append(root)
        while dq:
             node=dq.popleft()
             
             #print(node.val)
             if arr[i]!="#":
                node.left =TreeNode(int(arr[i]))
                dq.append(node.left)
             i+=1
             if arr[i]!="#":
                node.right=TreeNode(int(arr[i]))
                dq.append(node.right)
             i+=1
        return  root