https://leetcode.cn/problems/h54YBf/
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
难度：☆☆☆
题目：
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
代码1：BFS
Python
from collections import deque
class Codec:
def serialize(self, root):
if not root:
return ''
que = deque([root])
ans = []
while que:
node = que.popleft()
if node:
ans.append(str(node.val))
que.append(node.left)
que.append(node.right)
else:
ans.append('None')
return ','.join(ans)
def deserialize(self, data):
if not data:
return []
lst = data.split(',')
root = TreeNode(int(lst[0]))
que = deque([root])
i = 1 # 将root放入que，i默认为1，从1开始
while que:
node = que.popleft()
# 默认1，就是left
if lst[i] != 'None':
node.left = TreeNode(int(lst[i]))
que.append(node.left)
i += 1 # 不管是不是None，继续往下走
if lst[i] != 'None':
node.right = TreeNode(int(lst[i]))
que.append(node.right)
i += 1
return root
Java
public class Codec {
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder ans = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
TreeNode node = que.poll();
if (node != null) {
ans.append("" + node.val);
que.offer(node.left);
que.offer(node.right);
} else {
ans.append("null");
}
ans.append(",");
}
return ans.toString();
}
public TreeNode deserialize(String data) {
if (data == "") {
return null;
}
String[] lst = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(lst[0]));
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int i = 1;
while (!que.isEmpty()) {
TreeNode node = que.poll();
if (!"null".equals(lst[i])) {
node.left = new TreeNode(Integer.parseInt(lst[i]));
que.offer(node.left);
}
i++;
if (!"null".equals(lst[i])) {
node.right = new TreeNode(Integer.parseInt(lst[i]));
que.offer(node.right);
}
i++;
}
return root;
}
}
代码2：DFS
Python
class Codec:
def serialize(self, root):
if not root:
return 'None'
root.left = self.serialize(root.left)
root.right = self.serialize(root.right)
return str(root.val) + ',' + str(root.left) + ',' + str(root.right)
def deserialize(self, data):
def dfs(lst):
val = lst.pop(0)
if val == 'None':
return
root = TreeNode(int(val))
root.left = dfs(lst)
root.right = dfs(lst)
return root
dlst = data.split(',')
return dfs(dlst)
Java
public class Codec {
public String serialize(TreeNode root) {
if (root == null) {
return "null";
}
String left = serialize(root.left);
String right = serialize(root.right);
return root.val + "," + left + "," + right;
}
public TreeNode deserialize(String data) {
Queue<String> que = new LinkedList<>();
for (String val : data.split(",")) {
que.offer(val);
}
return dfs(que);
}
private TreeNode dfs(Queue<String> que) {
String val = que.poll();
if ("null".equals(val)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = dfs(que);
root.right = dfs(que);
return root;
}
}