序列化二叉树
通常应用的前序、中序、后序、层序遍历记录的二叉树的信息不残缺，即 惟一的输入序列可能对应着多种二叉树 可能性。
- 察看题目示例，序列化的字符串实际上是二叉树的“层序遍历”（BFS）后果，本文也采纳层序遍历。
题目剖析
能够发现法则
序列化 应用层序遍历实现。 反序列化 通过以上递推公式反推各节点在序列中的索引，进而实现。
序列化和反序列化
- Java 序列化就是指把 Java 对象转换为字节序列的过程
- Java 反序列化就是指把字节序列复原为 Java 对象的过程。
留神 **
- 为残缺示意二叉树，思考将叶节点下的 null 也记录 **
- stringObject.substring(start,stop): 一个新的字符串，该字符串值蕴含 stringObject 的一个子字符串，其内容是从 start 处到 stop-1 处的所有字符，其长度为 stop 减 start。就是坐标范畴是左闭右开，不包含 stop 那个索引对应的字符
题解
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
public class Codec {
// Encodes a tree to a single string.
// 这个是序列化
public String serialize(TreeNode root) {
// 利用队列进行打印，并且须要把 null 的也打印进去
if(root == null) return "[]";// 要留神办法的返回类型是 String
StringBuilder res = new StringBuilder("[");// 定义一个字符串缓冲流先把左侧括号加进去
// 定义一个队列用于退出字符串，并且还要先把根节点加进去，也能够不加前面单写一行加
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
while(!queue.isEmpty()){
//poll 从队列头部删除一个元素。队列是空的时候会返回 null
TreeNode node = queue.poll();
// 如果以后节点不是空的就退出字符串
if(node != null) {
// 而后出栈的节点的值退出字符缓冲流对象 还要记得加都好，时刻记得这是字符串
res.append(node.val+",");
// 而后把以后节点的左右节点持续入栈
queue.add(node.left);
queue.add(node.right);
}else{res.append("null,");}// 如果是空的也要退出 null
}
// 依照层排列结束了
res.deleteCharAt(res.length() - 1);// 要把最初一个字符串前面一起的那个逗号删掉
res.append("]");// 删掉之后再把数组的另一半字符串加到下面
return res.toString();// 而后再把字符缓冲流变成字符串}
// Decodes your encoded data to tree.
// 这个是反序列化
public TreeNode deserialize(String data) {
// 反序列化就是把输出的字符串再换成节点
if(data.equals("[]") ) return null;
// 将输出的一长串字符串用，裁进去取 1 是去掉一开始的 0 索引下的[符号
String[] str = data.substring(1,data.length() - 1).split(",");
// 因为序列化也是一层一层的，所以第一个字符就是根节点
TreeNode root = new TreeNode(Integer.parseInt(str[0]));// 将字符串里的数字字符转化成数字再变成节点
// 定义一个链表，先把根节点存进去
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
int i = 1;
while(!queue.isEmpty()){
//poll 从队列头部删除一个元素。队列是空的时候会返回 null
TreeNode node = queue.poll();
// 如果下一个字符的值不是 null
if(!str[i].equals("null")){
// 那以后节点的左节点 就是这个值
node.left = new TreeNode(Integer.parseInt(str[i]));
// 而后再把以后节点的左节点加进去
queue.add(node.left);
}
i++;
if(!str[i].equals("null")){
// 那以后节点的左节点 就是这个值
node.right = new TreeNode(Integer.parseInt(str[i]));
// 而后再把以后节点的左节点加进去
queue.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));还有一个速度比拟快的答案，用了递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();}
public void serialize(TreeNode root, StringBuilder sb){if(root == null){sb.append("null").append(",");
return;
}
sb.append(root.val).append(",");
serialize(root.left,sb);
serialize(root.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {if(data == null || data.length() == 0) return null;
String[] s = data.split(",");
LinkedList<String> nodes = new LinkedList<>();
for(String str : s){nodes.addLast(str);
}
return deserialize(nodes);
}
public TreeNode deserialize(LinkedList<String> nodes){if(nodes.isEmpty()) return null;
String first = nodes.removeFirst();
if(first.equals("null")) return null;
TreeNode root = new TreeNode(Integer.parseInt(first));
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));