Poison

297. Serialize and Deserialize Binary Tree

DFS
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
public class Codec {
private static final String NULL = "null";
private static final String COMMA = ",";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}

private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(COMMA);
return;
}

sb.append(root.val).append(COMMA);
serialize(root.left, sb); // 注意此处调用的函数不是入口函数
serialize(root.right, sb);
}

private static class IndexHolder {
private int index;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] strArray = data.split(COMMA);
IndexHolder indexHolder = new IndexHolder();
return deserialize(strArray, indexHolder);
}

private TreeNode deserialize(String[] strArray, IndexHolder indexHolder) {
if (strArray[indexHolder.index].equals(NULL)) {
indexHolder.index++; // 注意此处需要偏移索引,以跳过空节点
return null;
}

TreeNode root = new TreeNode(Integer.parseInt(strArray[indexHolder.index++]));
root.left = deserialize(strArray, indexHolder);
root.right = deserialize(strArray, indexHolder);
return root;
}

}
LL Parser
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
public class Codec {

private static final String NULL = "null";
private static final char LEFT_BRACKET = '(';
private static final char RIGHT_BRACKET = ')';

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// Grammar: T = (T) num (T) | null

StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}

private void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL);
return;
}

sb.append(LEFT_BRACKET);
serialize(root.left, sb);
sb.append(RIGHT_BRACKET);
sb.append(root.val);
sb.append(LEFT_BRACKET);
serialize(root.right, sb);
sb.append(RIGHT_BRACKET);
}

private static class IndexHolder {
private int index;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
IndexHolder indexHolder = new IndexHolder();

return deserialize(data, indexHolder);
}

private TreeNode deserialize(String data, IndexHolder indexHolder) {
if (data.charAt(indexHolder.index) == LEFT_BRACKET) {
indexHolder.index++; // skip left bracket
TreeNode root = new TreeNode(-1);
root.left = deserialize(data, indexHolder);
indexHolder.index++; // skip right bracket
root.val = parseInt(data, indexHolder);
indexHolder.index++; // skip left bracket
root.right = deserialize(data, indexHolder);
indexHolder.index++; // skip right bracket

return root;
} else {
indexHolder.index += 4;
return null;
}
}

private int parseInt(String data, IndexHolder indexHolder) {
int sign = 1;
if (data.charAt(indexHolder.index) == '-') {
sign = -1;
indexHolder.index++;
}

int value = 0;
while (Character.isDigit(data.charAt(indexHolder.index))) {
value = value * 10 + data.charAt(indexHolder.index) - '0';
indexHolder.index++;
}

return value * sign;
}
}
BFS
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
public class Codec {

private static final String NULL = "null";
private static final String COMMA = ",";

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
sb.append(node.val).append(COMMA);
queue.offer(node.left);
queue.offer(node.right);
} else {
sb.append(NULL).append(COMMA);
}
}

return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodeStrArray = data.split(COMMA);

String rootStr = nodeStrArray[0];
if (rootStr.equals(NULL)) {
return null;
}

TreeNode root = new TreeNode(Integer.parseInt(rootStr));
Queue<TreeNode> queue = new LinkedList<>(); // 队列中仅含有非空的节点
queue.offer(root);

int i = 1; // 即将处理的元素的索引
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// 此时 i 不会越界的原因为若 root 不为空,则一定含有子节点,因为我们序列化了空节点
if (!nodeStrArray[i].equals(NULL)) {
node.left = new TreeNode(Integer.parseInt(nodeStrArray[i]));
queue.offer(node.left);
}
i++;
if (!nodeStrArray[i].equals(NULL)) {
node.right = new TreeNode(Integer.parseInt(nodeStrArray[i]));
queue.offer(node.right);
}
i++;
}

return root;
}

}

关键在于序列化空节点。

Reference

297. Serialize and Deserialize Binary Tree
剑指 Offer 37. 序列化二叉树