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