题意：序列化是一个过程，将数据结构或者对象转化成位串，以便存进文件、缓冲区或者通过网络传输到对端再进行重构。
设计算法实现二叉树的序列化和降序列化，对算法无性能要求，仅需保证二叉树能被序列化成字符串，同时字符串能被降序列为二叉树。
【leetcode|297SerializeandDeserializeBinaryTree】声明：不要使用类的成员、全局、静态的变量去存储状态，因为序列化和非序列化都是针对对象的，是无状态的。
思路：类似BFS，数据结构队列，处理父节点时就需要处理孩子节点，否则无法建立父子之间的链接。
// Encodes a tree to a single string.
public String serialize(TreeNode root) { //BFS
if(root == null)
return "";
StringBuilder strBuilder = new StringBuilder();
Deque tree = new LinkedList<>();
tree.add(root);
strBuilder.append(root.val + " ");
//分隔符：“ ”
TreeNode node;
while(!tree.isEmpty()){
node = tree.removeFirst();
solChild(node, strBuilder, tree);
//孩子成对出现
}
return strBuilder.toString();
}private void solChild(TreeNode node, StringBuilder strBuilder, Deque tree) {
if(node.left != null){
strBuilder.append(node.left.val + " ");
tree.add(node.left);
}else {
strBuilder.append("* ");
}if(node.right != null){
strBuilder.append(node.right.val + " ");
tree.add(node.right);
}else {
strBuilder.append("* ");
} } // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals(""))
return null;
String[] strTokens = data.split(" ");
Deque tree = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(strTokens[0]));
tree.add(root);
int index = 1, ret;
while(!tree.isEmpty()){
TreeNode node = tree.removeFirst();
ret = revChild(node, strTokens, index, tree);
index = ret;
}
return root;
}//node:父节点 ---> strTokens[i]
private int revChild(TreeNode node, String[] strTokens, int index, Deque tree) {
if(strTokens[index].equals("*")){//null 左孩子
node.left = null;
} else{
node.left = new TreeNode(Integer.parseInt(strTokens[index]));
tree.add(node.left);
//add reference
}
index++;
if(strTokens[index].equals("*")){//null 右孩子
node.right = null;
} else{
node.right = new TreeNode(Integer.parseInt(strTokens[index]));
tree.add(node.right);
}
index++;
return index;
//下一个要处理的串
}推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络