网站欢迎页面 特效,wordpress 付费主题,关键词推广软件排名,东莞网站建设提供商【问题描述】[中等]
序列化是将一个数据结构或者对象转换为连续的比特位的操作#xff0c;进而可以将转换后的数据存储在一个文件或者内存中#xff0c;同时也可以通过网络传输到另一个计算机环境#xff0c;采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列…【问题描述】[中等]
序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。示例: 你可以将以下二叉树1/ \2 3/ \4 5序列化为 [1,2,3,null,null,4,5]
提示: 这与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。说明: 不要使用类的成员 / 全局 / 静态变量来存储状态你的序列化和反序列化算法应该是无状态的。
【解答思路】
1. 递归 DFS public class Codec {public String rserialize(TreeNode root, String str) {if (root null) {str null,;} else {str str.valueOf(root.val) ,;str rserialize(root.left, str);str rserialize(root.right, str);}return str;}public String serialize(TreeNode root) {return rserialize(root, );}public TreeNode rdeserialize(ListString l) {if (l.get(0).equals(null)) {l.remove(0);return null;}TreeNode root new TreeNode(Integer.valueOf(l.get(0)));l.remove(0);root.left rdeserialize(l);root.right rdeserialize(l);return root;}public TreeNode deserialize(String data) {String[] data_array data.split(,);ListString data_list new LinkedListString(Arrays.asList(data_array));return rdeserialize(data_list);}
};
2. BFS 层次遍历 public class Codec {public String serialize(TreeNode root) {if(root null) return [];StringBuilder res new StringBuilder([);QueueTreeNode queue new LinkedList() {{ add(root); }};while(!queue.isEmpty()) {TreeNode node queue.poll();if(node ! null) {res.append(node.val ,);queue.add(node.left);queue.add(node.right);}else res.append(null,);}res.deleteCharAt(res.length() - 1);res.append(]);return res.toString();}public TreeNode deserialize(String data) {if(data.equals([])) return null;String[] vals data.substring(1, data.length() - 1).split(,);TreeNode root new TreeNode(Integer.parseInt(vals[0]));QueueTreeNode queue new LinkedList() {{ add(root); }};int i 1;while(!queue.isEmpty()) {TreeNode node queue.poll();if(!vals[i].equals(null)) {node.left new TreeNode(Integer.parseInt(vals[i]));queue.add(node.left);}i;if(!vals[i].equals(null)) {node.right new TreeNode(Integer.parseInt(vals[i]));queue.add(node.right);}i;}return root;}
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {if (root null) {return ;}QueueTreeNode queue new LinkedListTreeNode();ListInteger res new LinkedListInteger();queue.offer(root);//BFSwhile (!queue.isEmpty()) {TreeNode curNode queue.poll();if (curNode ! null) {res.add(curNode.val);queue.offer(curNode.left);queue.offer(curNode.right);} else {res.add(null);}} return res.toString();
}// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {if (data.length() 0) {return null;}//将字符串还原为数组String[] preStr data.substring(1, data.length() - 1).split(,);Integer[] bfsOrder new Integer[preStr.length];for (int i 0; i preStr.length; i) {if (preStr[i].trim().equals(null)) {bfsOrder[i] null;} else {bfsOrder[i] Integer.parseInt(preStr[i].trim());}}QueueTreeNode queue new LinkedListTreeNode();TreeNode root new TreeNode(bfsOrder[0]);int cur 1;//通过 cur 指针依次给节点赋值queue.offer(root);while (!queue.isEmpty()) { TreeNode curNode queue.poll();if (bfsOrder[cur] ! null) {curNode.left new TreeNode(bfsOrder[cur]);queue.add(curNode.left);}cur; if (bfsOrder[cur] ! null) {curNode.right new TreeNode(bfsOrder[cur]);queue.add(curNode.right);}cur;}return root;
}
【总结】
1.先序遍历和中序遍历可以唯一的确定一个二叉树前提是元素必须不一样。其次如果二叉树的遍历考虑了 null那么不管什么遍历我们都能把二叉树还原。
2.List用法
1.list中添加获取删除元素 添加方法是.add(e) 获取方法是.get(index) 删除方法是.remove(index) 按照索引删除 .remove(Object o) 按照元素内容删除 2.list中是否包含某个元素 .containsObject o 返回true或者false 3.list中根据索引将元素数值改变(替换) 注意 .set(index, element); 和 .add(index, element)添加; 的不同 4.list中查看判断元素的索引 根据元素索引位置进行的判断 注意.indexOf 和 lastIndexOf最后一个的不同 5.利用list中索引位置重新生成一个新的list截取集合 方法 .subList(fromIndex, toIndex) .size() 该方法得到list中的元素数的和
3.前中后序遍历变化的是[中]的位置左到右的顺序不改变
前序遍历 中左右中序遍历 左中右后续遍历 左右中
参考链接https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-le-2/ 参考链接https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-55/ 参考链接链接https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/
List用法详解https://blog.csdn.net/Barcon/article/details/82628120
