序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。
提示:
树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000
private void dfs(TreeNode root) {
// 终止条件是发现入参为空
if(null==root) {
return;
}
// 1. 根
处理root的代码
// 2. 左
dfs(root.left);
// 3. 右
dfs(root.right);
}
private StringBuilder serializeRes;
public String serialize(TreeNode root) {
if (null==root) {
return null;
}
serializeRes = new StringBuilder();
serializeDfs(root);
return serializeRes.toString();
}
private void serializeDfs(TreeNode root) {
if(null==root) {
serializeRes.append("n,");
return;
}
// 1. 根
serializeRes.append(root.val).append(",");
// 2. 左
serializeDfs(root.left);
// 3. 右
serializeDfs(root.right);
}
1,2,n,n,3,n,n,
private String[] deserializeArray;
private int deserializeOffset;
public TreeNode deserialize(String data) {
if (null==data) {
return null;
}
deserializeArray = data.split(",");
deserializeOffset = 0;
return deserializeDfs();
}
private TreeNode deserializeDfs() {
if (deserializeOffset>=deserializeArray.length) {
return null;
}
if ("n".equals(deserializeArray[deserializeOffset])) {
deserializeOffset++;
return null;
}
// 1. 根
TreeNode treeNode = new TreeNode(Integer.valueOf(deserializeArray[deserializeOffset++]));
// 2. 左
treeNode.left = deserializeDfs();
// 3. 右
treeNode.right = deserializeDfs();
return treeNode;
}
public class Codec {
// 本题的整体思路是前序遍历,即:根左右
private StringBuilder serializeRes;
private String[] deserializeArray;
private int deserializeOffset;
private void serializeDfs(TreeNode root) {
if(null==root) {
serializeRes.append("n,");
return;
}
// 1. 根
serializeRes.append(root.val).append(",");
// 2. 左
serializeDfs(root.left);
// 3. 右
serializeDfs(root.right);
}
private TreeNode deserializeDfs() {
if (deserializeOffset>=deserializeArray.length) {
return null;
}
if ("n".equals(deserializeArray[deserializeOffset])) {
deserializeOffset++;
return null;
}
// 1. 根
TreeNode treeNode = new TreeNode(Integer.valueOf(deserializeArray[deserializeOffset++]));
// 2. 左
treeNode.left = deserializeDfs();
// 3. 右
treeNode.right = deserializeDfs();
return treeNode;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (null==root) {
return null;
}
serializeRes = new StringBuilder();
serializeDfs(root);
return serializeRes.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (null==data) {
return null;
}
deserializeArray = data.split(",");
deserializeOffset = 0;
return deserializeDfs();
}
}
1,2,n,n,3,n,n,