297. Serialize and Deserialize Binary Tree
题目:
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.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"
, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
链接: http://leetcode.com/problems/serialize-and-deserialize-binary-tree/
题解:
序列化Binary Tree。 这里因为给定的Tree的val是Integer,所以我们可以用一个字符型的常量当做delimiter,比如','。然后我们可以使用两种方法, pre-order traversal,或者level-order traversal。两种方法的时间复杂度和空间复杂度都一样。下面是pre-order traversal的:
Time Complexity - O(n), Space Compleixty - O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String delimiter = ",";
private final String emptyNode = "#"; // Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
} private void serialize(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append(emptyNode).append(delimiter);
} else {
sb.append(root.val).append(delimiter);
serialize(root.left, sb);
serialize(root.right, sb);
}
} // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(delimiter)));
return deserialize(nodes);
} private TreeNode deserialize(Deque<String> nodes) {
String nodeVal = nodes.pollFirst();
if(nodeVal.equals(emptyNode)) {
return null;
} else {
TreeNode node = new TreeNode(Integer.parseInt(nodeVal));
node.left = deserialize(nodes);
node.right = deserialize(nodes);
return node;
}
}
} // Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
二刷:
总的来说就是用in-order traversal来遍历。 Serialize的时候用一个StringBuilder保存。 Deserialize的时候先根据delimiter把元素都split到一个String[]数组里,然后可以把元素放入queue中,接下来递归使用in-order traversal方法来重建树。重建时每次从queue的前部poll()就可以了。
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String delimiter = ",";
private final String nullNode = "#"; // Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
//sb.setLength(sb.length() - 1);
return sb.toString();
} private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(nullNode).append(delimiter);
} else {
sb.append(root.val).append(delimiter);
serialize(root.left, sb);
serialize(root.right, sb);
}
} // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) return null;
String[] strs = data.split(delimiter);
Queue<String> q = new LinkedList<>();
Collections.addAll(q, strs);
return deserialize(q);
} private TreeNode deserialize(Queue<String> q) {
if (q.isEmpty()) return null;
String val = q.poll();
if (val.equals(nullNode)) return null;
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = deserialize(q);
node.right = deserialize(q);
return node;
}
} // Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
三刷:
还是使用了in-order traversal。要注意delimiter假如使用'|'会报错,也不知道为什么。
Java:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String nullNode = "#";
private final String delimiter = ","; // Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
} private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(nullNode).append(delimiter);
return;
}
sb.append(root.val).append(delimiter);
serialize(root.left, sb);
serialize(root.right, sb);
} // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>();
Collections.addAll(q, data.split(delimiter));
return deserialize(q);
} private TreeNode deserialize(Queue<String> q) {
if (q.isEmpty()) return null;
String s = q.poll();
TreeNode root = null;
if (!s.equals(nullNode)) {
root = new TreeNode(Integer.valueOf(s));
root.left = deserialize(q);
root.right = deserialize(q);
}
return root;
}
} // Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Reference:
http://articles.leetcode.com/2010/09/serializationdeserialization-of-binary.html
http://articles.leetcode.com/2010/09/saving-binary-search-tree-to-file.html
https://leetcode.com/discuss/66147/recursive-preorder-python-and-c-o-n
https://leetcode.com/discuss/66117/easy-to-understand-java-solution
https://leetcode.com/discuss/66698/java-bfs-based-accepted-solution-using-queue
https://leetcode.com/discuss/66181/easy-to-understand-java-solution
https://leetcode.com/discuss/69390/simple-solution-%23preorder-traversal-%23recursive-%23simple-logic
https://leetcode.com/discuss/66077/c-accepted-o-n-easy-solution
https://leetcode.com/discuss/66397/java-stack-based-solution-using-json
https://leetcode.com/discuss/66076/java-solution-with-queue
https://leetcode.com/discuss/66625/a-level-order-traversal-solution
https://leetcode.com/discuss/66141/a-48-ms-rough-c-solution-used-queue
最新文章
- 从零开始编写自己的C#框架(23)——上传组件使用说明
- Intent
- Webstorm功能详解及插件推荐
- css样式多个类、标签用【逗号 空格 冒号 点】分开的解析
- POSIX正则表达式
- Pyqt QListWidget 展示系统环境变量
- rsync+inotify-tools文件实时同步
- 10本最新的Android开发电子书免费下载
- ASP.NET项目中引用全局dll
- WP-Syntax 插件使用方法
- Mac Vim 如何设置高亮
- JSP前端总结
- 8.PHP 教程_PHP字符串
- CSS图形形状大全
- 06_NoSQL数据库之Redis数据库:Redis的高级应用之登录授权和主从复制
- PHP取一算法
- Vue2.0 $set()的正确使用方式
- kafka 单机配置
- HDU 1879	继续畅通工程(最小生成树)
- cocos源码分析--用Sprite加载自定义着色器
热门文章
- html表格属性
- CS小分队第一阶段冲刺站立会议(5月7日)
- MVC4 网站发布(整理 + 部分转载 + 部分问题收集和解决方案)
- mono for andorid 引用外部的dll问题
- hdu 1028 Ignatius and the Princess III
- GS初始化
- 关于High-Resolution Timer(了解)
- 引擎设计跟踪(九.14.2h) 开发计划
- Codeforces Round #204 (Div. 2)->;D. Jeff and Furik
- Hadoop分布式配置