序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
普通二叉树序列化与反序列化
题目描述
序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改。序列化的结果是一个字符串,序列化时通过某种符号表示空节点(null),以 ,
表示一个结点值的结束(null,)。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树:
1
/ \ 2 3 / \ 4 5
序列化为 “[1,2,3,null,null,4,5]”
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private StringBuilder serializeCore(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("null,");
} else {
// 先序遍历的次序序列化
sb.append(root.val + ",");
sb = serializeCore(root.left, sb);
sb = serializeCore(root.right, sb);
}
return sb;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return serializeCore(root, new StringBuilder()).toString();
}
private TreeNode deserializeCore(List<String> list) {
if ("null".equals(list.get(0))) {
list.remove(0);
return null;
}
// 先序遍历的次序还原
TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
list.remove(0);
root.left = deserializeCore(list);
root.right = deserializeCore(list);
return root;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String str) {
String[] strArray = str.split(",");
List<String> list = new ArrayList<>(Arrays.asList(strArray));
return deserializeCore(list);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
二叉搜索树的序列化和反序列化
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
注意:不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/serialize-and-deserialize-bst 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码
public class Codec {
private StringBuilder postOrder(TreeNode root, StringBuilder sb) {
if (root == null) return sb;
sb.append(root.val);
sb.append(',');
postOrder(root.left, sb);
postOrder(root.right, sb);
return sb;
}
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = postOrder(root, new StringBuilder());
if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
private TreeNode helper(List<String> list, int lower, int upper) {
if (list.isEmpty()) return null;
int val = Integer.parseInt(list.get(0));
if (val < lower || val > upper) return null;
list.remove(0);
TreeNode root = new TreeNode(val);
root.left = helper(list, lower, val);
root.right = helper(list, val, upper);
return root;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) return null;
List<String> list = new ArrayList<>(Arrays.asList(data.split(",")));
return helper(list, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));