题目描述
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树
解答
树中节点值不重复的情况下可使用如下方法.
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
|
String Serialize(TreeNode root) {
StringBuilder pre = new StringBuilder();
getPreOrder(root, pre);
StringBuilder in = new StringBuilder();
getInOrder(root, in);
return pre + ";" + in;
}
private void getInOrder(TreeNode root, StringBuilder builder) {
if (root == null) {
return;
}
getInOrder(root.left, builder);
builder.append(root.val + ",");
getInOrder(root.right, builder);
}
private void getPreOrder(TreeNode root, StringBuilder builder) {
if (root == null) {
return;
}
builder.append(root.val + ",");
getPreOrder(root.left, builder);
getPreOrder(root.right, builder);
}
TreeNode Deserialize(String str) {
String[] strs = str.split(";");
if (strs.length == 0) {
return null;
}
String[] pre = strs[0].split(",");
String[] in = strs[1].split(",");
TreeNode root = buildTree(pre, in);
return root;
}
private TreeNode buildTree(String[] pre, String[] in) {
if (pre == null || pre.length == 0) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(pre[0]));
int leftNum = 0;
for (int i = 0; i < in.length; i++) {
if (in[i].equals(pre[0])) {
leftNum = i;
break;
}
}
root.left = buildTree(Arrays.copyOfRange(pre, 1, leftNum + 1), Arrays.copyOfRange(in, 0, leftNum));
root.right = buildTree(Arrays.copyOfRange(pre, leftNum + 1, pre.length), Arrays.copyOfRange(in, leftNum + 1, in.length));
return root;
}
|
官方题解
链接：https://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84?answerType=1&f=discussion
来源：牛客网
方法一：先序遍历实现
预备知识：先序遍历的递归实现：
1
2
3
4
5
6
7
8
9
10
| void pre_order(TreeNode *root) {
if (!root) {
return;
}
pre_order(root->left);
pre_order(root->right);
}
|
对于本题来说，可以套用上述模板。
假设序列化的结果为字符串 str, 初始str = “”.根据要求，遇到nullptr节点，str += “#”
遇到非空节点，str += “val” + “!”; 假设val为3， 就是 str += “3!”
所以，最终的代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| char* Serialize(TreeNode *root) {
if (!root) {
return "#";
}
string res = to_string(root->val);
res.push_back(',');
char* left = Serialize(root->left);
char* right = Serialize(root->right);
char* ret = new char[strlen(left)+strlen(right)+res.size()];
strcpy(ret,res.c_str());
strcat(ret,left);
strcat(ret,right);
return ret;
}
|
反序列化的结果，就是根据先序遍历，再重建二叉树即可。
代码如下：
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
|
TreeNode* deseri(char *&s) {
if (*s == '#') {
++s;
return nullptr;
}
int num = 0;
while (*s != ',') {
num = num * 10 + (*s - '0');
++s;
}
++s;
TreeNode *root = new TreeNode(num);
root->left = deseri(s);
root->right = deseri(s);
return root;
}
TreeNode* Deserialize(char *str) {
return deseri(str);
}
|
中序遍历，后序遍历大致都差不多。
方法二：层次遍历实现
层次遍历采用队列实现。跟先序遍历的思想差不多，无非都是把树的所有数据遍历一遍，然后记录下来。
层次遍历模板：
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
| void bfs(TreeNode *root){
queue<TreeNode*> qt;
qt.push(root);
string s;
while (!qt.empty())
{
TreeNode *node = qt.front();
qt.pop();
if (node == NULL)
{
s.push_back('#');
s.push_back(',');
continue;
}
s += to_string(node->val);
s.push_back(',');
qt.push(node->left);
qt.push(node->right);
}
}
|
序列化的操作直接根据模板套即可。代码如下：
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
| char* Serialize(TreeNode *root)
{
string s;
queue<TreeNode*> qt;
qt.push(root);
while (!qt.empty())
{
TreeNode *node = qt.front();
qt.pop();
if (node == nullptr)
{
s.push_back('N');
s.push_back(',');
continue;
}
s += to_string(node->val);
s.push_back(',');
qt.push(node->left);
qt.push(node->right);
}
char *ret = new char[s.length() + 1];
strcpy(ret, s.c_str());
return ret;
}
|
反序列化就是根据层次遍历在走一遍即可。
代码如下：
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
| TreeNode* Deserialize(char *str)
{
if (str == nullptr) {
return nullptr;
}
string s(str);
if (str[0] == '#') {
return nullptr;
}
queue<TreeNode*> nodes;
TreeNode *ret = new TreeNode(atoi(s.c_str()));
s = s.substr(s.find_first_of(',') + 1);
nodes.push(ret);
while (!nodes.empty() && !s.empty())
{
TreeNode *node = nodes.front();
nodes.pop();
if (s[0] == '#')
{
node->left = nullptr;
s = s.substr(2);
}
else
{
node->left = new TreeNode(atoi(s.c_str()));
nodes.push(node->left);
s = s.substr(s.find_first_of(',') + 1);
}
if (s[0] == '#')
{
node->right = nullptr;
s = s.substr(2);
}
else
{
node->right = new TreeNode(atoi(s.c_str()));
nodes.push(node->right);
s = s.substr(s.find_first_of(',') + 1);
}
}
return ret;
}
|
此题主要考察对树的遍历和构造树。