本文共 4878 字，大约阅读时间需要 16 分钟。
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
deserialize()是看了九章的答案才写出来的，主要卡壳的地方是不知道怎样把数据取出来。涉及到从字符串中提取数据的题要想到split()函数！！！
serialize()我的写法和答案不太一样，性能会差一些。用BFS把所有的当前节点和其子节点加入ArrayList，再将其转成String public class Codec { public String serialize(TreeNode root) { if(root == null) return "{}"; LinkedList queue = new LinkedList<>(); ArrayList res = new ArrayList<>(); queue.addLast(root); res.add(root.val); while(!queue.isEmpty()) { TreeNode cur = queue.pollFirst();//poll会删除元素，get和peek都不会！ if(cur != null) { if(cur.left != null) { res.add(cur.left.val); queue.addLast(cur.left); } else { res.add(null); } if(cur.right != null) { res.add(cur.right.val); queue.addLast(cur.right); } else { res.add(null); } } } return res.toString(); } public TreeNode deserialize(String data) { if(data.length() < 3) return null; String[] str = data.substring(1, data.length() - 1).split(", "); ArrayList queue = new ArrayList<>(); TreeNode root = new TreeNode(Integer.parseInt(str[0])); queue.add(root); int index = 0; boolean isLeftChild = true; for(int i = 1; i < str.length; i++) { TreeNode cur = queue.get(index); if(!str[i].equals("null")) { TreeNode node = new TreeNode(Integer.parseInt(str[i])); if(isLeftChild) { cur.left = node; } else { cur.right = node; } queue.add(node); } if(!isLeftChild) { index++; } isLeftChild = !isLeftChild; } return root; }} jiuzhang solution: BFS
注意！序列化函数这里的队列一定要用ArrayList，用LinkedList会比前者慢40倍。 public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "{}"; ArrayList queue = new ArrayList<>(); queue.add(root); //BFS将非null的当前节点和其子节点（可能为null）加入queue for(int i = 0; i < queue.size(); i++) { TreeNode cur = queue.get(i); if(cur != null) { queue.add(cur.left); queue.add(cur.right); } else { continue; } } //删除末尾多余的"#" while (queue.get(queue.size() - 1) == null) { queue.remove(queue.size() - 1); } //用StringBuilder构建字符串，StringBuffer线程安全但是速度更慢 StringBuilder strBuild = new StringBuilder(); strBuild.append("{"); strBuild.append(queue.get(0).val); for(int i = 1; i < queue.size(); i++) { if(queue.get(i) == null) { strBuild.append(",#"); } else { strBuild.append(","); strBuild.append(queue.get(i).val); } } strBuild.append("}"); return strBuild.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.length() < 3) return null; //去除","并将每一个结点放入字符串数组中 String[] str = data.substring(1, data.length() - 1).split(","); ArrayList queue = new ArrayList<>(); TreeNode root = new TreeNode(Integer.parseInt(str[0])); //开始已经判断过空的情况，因此数组的第一个值一定是有效的数字 queue.add(root); int index = 0; boolean isLeftChild = true; for(int i = 1; i < str.length; i++) { TreeNode cur = queue.get(index); if(!str[i].equals("#")) { TreeNode node = new TreeNode(Integer.parseInt(str[i])); if(isLeftChild) { cur.left = node; } else { cur.right = node; } queue.add(node); } //当前节点的左结点和右结点都添加完成后再操作下一个 if(!isLeftChild) { index++; } isLeftChild = !isLeftChild; } return root; }} 转载地址：http://skqvb.baihongyu.com/