My Personal Time

Desire is the starting point of all achievement

0%

LeetCode-二叉树的序列化与反序列化

题目来源

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

思路

根据前序遍历的顺序来序列化二叉树,因为前序遍历是从根节点开始的,在遍历到null节点的时候,可以将null节点序列化为字符串”null“,反序列化也是按照前序遍历递归的重建二叉树。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package le;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class le_297 {
class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){val=x;}
}

public String serialize(TreeNode root){
if(root==null){
return "null,";
}
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(root.val + ",");
stringBuilder.append(serialize(root.left));
stringBuilder.append(serialize(root.right));
return stringBuilder.toString();
}

public TreeNode deserialize(String data){
String[] strings = data.split(",");
Queue<String> queue = new ArrayDeque<>(Arrays.asList(strings));
return func(queue);
}

private TreeNode func(Queue<String> queue) {
String string = queue.remove();
if("null".equals(string)){
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(string));
node.left = func(queue);
node.right = func(queue);
return node;
}
}