题目描述：序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
提示：
- 树中结点数在范围
[0, 104] 内
-1000 <= Node.val <= 1000
代码实现
前序实现
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| class Codec {
private final static String NULL_NODE = "#";
private final static String SEPARATOR = ",";
public String serialize(TreeNode root) {
if (root == null) {
return NULL_NODE;
}
return String.valueOf(root.val) + SEPARATOR + serialize(root.left) + SEPARATOR + serialize(root.right);
}
public TreeNode deserialize(String data) {
String[] allNodeVal = data.split(SEPARATOR);
LinkedList<String> nodes = new LinkedList<>();
for (String nodeVal : allNodeVal) {
nodes.addLast(nodeVal);
}
return deserialize(nodes);
}
public TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
String firstVal = nodes.removeFirst();
if (NULL_NODE.equals(firstVal)) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(firstVal));
node.left = deserialize(nodes);
node.right = deserialize(nodes);
return node;
}
}
|
后序实现
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| class Codec {
private final static String NULL_NODE = "#";
private final static String SEPARATOR = ",";
public String serialize(TreeNode root) {
if (root == null) {
return NULL_NODE;
}
return serialize(root.left) + SEPARATOR + serialize(root.right) + SEPARATOR + String.valueOf(root.val);
}
public TreeNode deserialize(String data) {
String[] nodes = data.split(SEPARATOR);
LinkedList<String> list = new LinkedList<>();
for (String node : nodes) {
list.addFirst(node);
}
return deserialize(list);
}
public TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty()) {
return null;
}
String firstVal = nodes.removeFirst();
if (NULL_NODE.equals(firstVal)) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(firstVal));
root.right = deserialize(nodes);
root.left = deserialize(nodes);
return root;
}
}
|
中序实现
中序只能序列化，无法反序列化
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
| class Codec {
private final static String NULL_NODE = "#";
private final static String SEPARATOR = ",";
public String serialize(TreeNode root) {
if (root == null) {
return NULL_NODE;
}
return serialize(root.left) + SEPARATOR + String.valueOf(root.val) + SEPARATOR + serialize(root.right);
}
public TreeNode deserialize(String data) {
return 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| class Codec {
private final static String NULL_NODE = "#";
private final static String SEPARATOR = ",";
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
return null;
}
LinkedList<TreeNode> list = new LinkedList<>();
list.addLast(root);
while (!list.isEmpty()) {
TreeNode node = list.removeFirst();
if (node == null) {
sb.append(NULL_NODE).append(SEPARATOR);
continue;
}
sb.append(node.val).append(SEPARATOR);
list.addLast(node.left);
list.addLast(node.right);
}
return sb.substring(0, sb.length() - 1);
}
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
String[] nodes = data.split(SEPARATOR);
LinkedList<TreeNode> list = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
list.addLast(root);
for (int i = 1; i < nodes.length; ) {
TreeNode parent = list.removeFirst();
String left = nodes[i++];
if (NULL_NODE.equals(left)) {
parent.left = null;
} else {
parent.left = new TreeNode(Integer.parseInt(left));
list.addLast(parent.left);
}
String right = nodes[i++];
if (NULL_NODE.equals(right)) {
parent.right = null;
} else {
parent.right = new TreeNode(Integer.parseInt(right));
list.addLast(parent.right);
}
}
return root;
}
}
|