297. Serialize and Deserialize Binary Tree
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
先序遍历
每个节点用逗号分隔，空节点使用#表示。序列化二叉树肯定会想到先序、中序、后序、层次遍历四种，中序和后序从下往上推不好实现，剩下的考虑先序和层次。而先序遍历之所以可以应用，是因为每个分支都有明确的结束标记。序列化的时候，先确定自己，再确定左右。反序列化的过程，先获取头部，再判断左子节点，左子节点有结束边界，之后右子节点也按照边界结束。
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
|
public String serialize(TreeNode root) {
if (root == null) {
return "#,";
}
String curStr = root.val + ",";
String leftStr = serialize(root.left);
String rightStr = serialize(root.right);
return curStr + leftStr + rightStr;
}
public TreeNode deserialize(String data) {
if (data == null) {
return null;
}
String[] strArr = data.split(",");
Queue<String> queue = new LinkedList<>();
for (String str : strArr) {
queue.offer(str);
}
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
String str = queue.poll();
if (str.equals("#")) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(str));
node.left = deserialize(queue);
node.right = deserialize(queue);
return node;
}
|
层次遍历
层次遍历写起来稍微有点复杂，但是更好理解。序列化的时候，先把顶部节点放至 queue 中，依据左右节点值放至 StringBuilder 中，再按照是否为空，将不为空的放入队列中进行下一层的遍历。反序列化同样是新建一个队列放入头结点，将左右节点非空的放入队列中，进行下一层的从左到右的解析。
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 String serialize(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder().append(root.val).append(",");
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
TreeNode right = node.right;
if (left != null) {
sb.append(left.val).append(",");
queue.offer(left);
} else {
sb.append("#,");
}
if (right != null) {
sb.append(right.val).append(",");
queue.offer(right);
} else {
sb.append("#,");
}
}
return sb.toString();
}
public TreeNode deserialize(String data) {
if (data == null || data == "") {
return null;
}
String[] strArr = data.split(",");
int index = 0;
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = buildNode(strArr[0]);
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = buildNode(strArr[++index]);
TreeNode right = buildNode(strArr[++index]);
node.left = left;
node.right = right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
return root;
}
private TreeNode buildNode(String str) {
if ("#".equals(str)) {
return null;
}
return new TreeNode(Integer.parseInt(str));
}
|
