友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 Clarification: The above format is the same as <a href="/faq/#binary-tree">how LeetCode serializes a binary tree</a>. 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.
解题分析
一个比较简单的思路是分层进行序列化。这里一个误区就是把二叉树按照满二叉树转化成一个数组形式。
一个解决办法就是：在序列化的时候，先出力父节点，然后循环调用处理子节点，这样的话，就会把父子节点的关联关系给用上，也可以正常应对极端不平衡的情况。
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
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "#!";
}
String result = root.val + "!";
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.left != null) {
result += root.left.val + "!";
queue.offer(root.left);
} else {
result += "#!";
}
if (root.right != null) {
result += root.right.val + "!";
queue.offer(root.right);
} else {
result += "#!";
}
}
return result;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] values = data.split("!");
int index = 0;
TreeNode head = generate(values[index++]);
Queue<TreeNode> queue = new LinkedList<>();
if (head != null) {
queue.offer(head);
}
TreeNode node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generate(values[index++]);
node.right = generate(values[index++]);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return head;
}
private TreeNode generate(String val) {
if ("#".equals(val)) {
return null;
}
return new TreeNode(Integer.parseInt(val));
}
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
/**
* 参考左程云
*/
public String serialize(TreeNode root) {
if (root == null) {
return "#!";
}
String result = root.val + "!";
result += serialize(root.left);
result += serialize(root.right);
return result;
}
public TreeNode deserialize(String data) {
if (data == null || data.isEmpty()) {
return null;
}
String[] values = data.split("!");
Queue<String> queue = new LinkedList<>();
for (String value : values) {
queue.offer(value);
}
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
if (queue.isEmpty()) {
return null;
}
String value = queue.poll();
if (value.equals("#")) {
return null;
}
TreeNode head = new TreeNode(Integer.parseInt(value));
head.left = deserialize(queue);
head.right = deserialize(queue);
return head;
}
这里有一个思维误区：总感觉如果二叉树有大量空节点（比如左子树只有左边有值，右子树只要右边有值），无法正常进行序列化！但是，实际这里是错误的感觉！在进行递归序列化时，递归调用到每棵树时，会被当前节点的左右节点都做一下序列化，那么没有值的节点会被处理成 ，这样，当前节点和左右子节点都会被标识出来。不会漏标或者错标。另外需要注意，叶子节点也会产生两个 值来表示叶子节点的子节点，这点和前序遍历不一样。看下图：
