序列化二叉树
通常应用的前序、中序、后序、层序遍历记录的二叉树的信息不残缺，即惟一的输入序列可能对应着多种二叉树可能性。
- 察看题目示例，序列化的字符串实际上是二叉树的 “层序遍历”（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));