题目描述
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
样例：二叉树{3,9,20,#,#,15,7}
数结构如下：
思路
序列化：其实就是如何遍历二叉树。
因为不知道二叉树有多少个节点，所以考虑ArrayList。
因为考虑到要反序列化，所以对空的子节点，其val用“#”标识。
因为是动态的添加字符到字符串，考虑StringBuilder。
- 初始化List和StringBuilder
先取root的val，append到StringBuilder。然后把root add到List。
- 遍历list，将当前节点的左右子节点add到List，将子节点的val append到StringBuilder
- 如果子节点为null，将”#”append到StringBuilder
反序列化：其实就是根据字符串恢复二叉树。
首先将字符串处理成String[]{val1,val2,val3 …}的形式
用val1创建root
因为String[]保存的是完全二叉树的val（空节点为”#”），考虑遍历String[]恢复二叉树
因为不知道二叉树包含多少个节点，考虑用ArrayList保存节点
用Index指向当前恢复的节点在List中的下标
- 遍历String[]
- 读完一组val，创建左右子节点并加入List，当前节点的left、right指向子节点，index++
- 如果读到“#”，不创建子节点，但读完一组后，index++（因为要准确恢复二叉树）
代码
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
| public String serialize(TreeNode root) {
if(root == null) return null;
StringBuilder sBuilder = new StringBuilder("{");
sBuilder.append(root.val);
ArrayList<TreeNode> aList = new ArrayList<TreeNode>();
aList.add(root);
for(int i = 0; i < aList.size(); i++) {
if(aList.get(i) == null) continue;
aList.add(aList.get(i).left);
aList.add(aList.get(i).right);
if(aList.get(i).left != null) {
sBuilder.append("," + aList.get(i).left.val);
}else {
sBuilder.append(",#");
}
if(aList.get(i).right != null) {
sBuilder.append("," + aList.get(i).right.val);
}else {
sBuilder.append(",#");
}
}
sBuilder.append("}");
return sBuilder.toString();
}
public TreeNode deserialize(String data) {
if(data == null) return null;
String[] strings = data.substring(1, data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
ArrayList<TreeNode> aList = new ArrayList<TreeNode>();
aList.add(root);
int index = 0;
boolean isLeft = true;
for(int i = 1; i < strings.length; i++) {
if(!strings[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(strings[i]));
if(isLeft) {
aList.get(index).left = node;
aList.add(node);
}else {
aList.get(index).right = node;
aList.add(node);
}
}
isLeft = !isLeft;
if(isLeft) index++;
}
return root;
}
|
考差点
- 二叉树的遍历（用ArrayList保存当前读取的节点和子节点
将要读取的节点）
- 二叉树的还原（用ArrayList保存当前恢复的节点和其指向的子节点
将要恢复的节点）