LeetCode 297.Serialize And Deserialize Binary Tree
原创LeetCode 297.Serialize And Deserialize Binary Tree
原创
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.
Example:
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"题目大意：讲一个二叉树进行序列化和反序列化
解法一：
前序的序列化和反序列化。
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null ) return "#!";
return root.val+"!"+serialize(root.left)+serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null||data.length() == 0) return null;
String[] values = data.split("!");
List<String> list = new LinkedList<>(Arrays.asList(values));
return deserialize(list);
}
public TreeNode deserialize(List<String> list){
String string = list.remove(0);
if (string.equals("#")){
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(string));
node.left = deserialize(list);
node.right = deserialize(list);
return node;
}前序序列化一个二叉树，节点为空的的用#代替，不管数字还是#后面都添加一个！作为分隔符，以免造成歧义；
解法二：
层序的序列化和反序列化。
// Encodes a tree to a single string.
public String serializeByLevel(TreeNode root) {
String res ="";
if (root == null ){
return "#!";
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
res += root.val+"!";
while (!queue.isEmpty()){
TreeNode temp = queue.remove();
if (temp.left!=null)
{
queue.add(temp.left);
res += temp.left.val+"!";
} else res += "#!";
if (temp.right!=null){
queue.add(temp.right);
res += temp.right.val+"!";
}else res += "#!";
}
return res;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String string) {
if (string == null||string.length()==0) return null;
String [] values = string.split("!");
Queue<String> queue = new LinkedList<>();
for (String str:values){
queue.add(str);
}
Queue<TreeNode> queue1 = new LinkedList<>();
String first = queue.remove();
if (first.equals("#")) return null;
TreeNode root = new TreeNode(Integer.valueOf(first));
queue1.add(root);
deSerializeByLevelHelper(queue,queue1);
return root;
}
public void deSerializeByLevelHelper(Queue<String>queue,Queue<TreeNode>queue1){
String str;
TreeNode temp;
while (!queue1.isEmpty()){
str = queue.remove();
temp = queue1.remove();
if (str.equals("#")){
temp.left = null;
}else {
temp.left = new TreeNode(Integer.valueOf(str));
queue1.add(temp.left);
}
str = queue.remove();
if (str.equals("#")){
temp.right = null;
}else {
temp.right = new TreeNode(Integer.valueOf(str));
queue1.add(temp.right);
}
}
}
层序的反序列化较为复杂。
关于层序的反序列化的另一种方法:(其实跟上面的方法大同小异)
public TreeNode deserialize(String levelStr){
String[] values = levelStr.split("!");
int index = 0;
TreeNode head = generateNodeByString(values[index++]);
Queue<TreeNode> queue = new LinkedList<>();
if (head!=null){
queue.offer(head);
}
TreeNode node = null;
while (!queue.isEmpty()){
node = queue.poll();
node.left = generateNodeByString(values[index++]);
node.right = generateNodeByString(values[index++]);
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}return head;
}
public TreeNode generateNodeByString(String val){
if (val.equals("#")) return null;
return new TreeNode(Integer.valueOf(val));
}总结：
序列化与反序列化，采用前中后序较为简单，层序的反序列化较为复杂。重点注意前序反序列化的参数技巧。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。