#描述 这是一篇针对初学者的题解，共用两种方法解决。 知识点：二叉树，先序遍历，层次遍历 难度：二星
#题解 题目描述：给定一颗二叉树，将其序列化和反序列化。
##方法一：先序遍历实现 预备知识：先序遍历的递归实现：
void pre_order(TreeNode *root) {
if (!root) {
return;
}
// process root
// ...
pre_order(root->left);
pre_order(root->right);
}
对于本题来说，可以套用上述模板。 假设序列化的结果为字符串 str, 初始str = "".根据要求，遇到nullptr节点，str += "#" 遇到非空节点，str += "val" + "!"; 假设val为3， 就是 str += "3!"
所以，序列化二叉树的代码为：
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()];
// 如果是string类型，直接用operator += ,这里char* 需要用函数
strcpy(ret,res.c_str());
strcat(ret,left);
strcat(ret,right);
return ret;
}
反序列化的结果，就是根据先序遍历，再重建二叉树即可。 代码如下：
// 参数使用引用&， 以实现全局变量的目的
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);
}
所以，最终的代码如下：
class Solution {
public:
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()];
// 如果是string类型，直接用operator += ,这里char* 需要用函数
strcpy(ret,res.c_str());
strcat(ret,left);
strcat(ret,right);
return ret;
}
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);
}
};
中序遍历，后序遍历大致都差不多。
##方法二：层次遍历实现 层次遍历采用队列实现。跟先序遍历的思想差不多，无非都是把树的所有数据遍历一遍，然后记录下来。 层次遍历模板：
void bfs(TreeNode *root){
queue<treenode*> qt;
qt.push(root);
string s;
while (!qt.empty())
{
// pop operator
TreeNode *node = qt.front();
qt.pop();
// process node
if (node == NULL)
{
s.push_back('#');
s.push_back(',');
continue;
}
s += to_string(node->val);
s.push_back(',');
// push operator
qt.push(node->left);
qt.push(node->right);
}
}
序列化的操作直接根据模板套即可。代码如下：
char* Serialize(TreeNode *root)
{
string s;
queue<TreeNode*> qt;
qt.push(root);
while (!qt.empty())
{
// pop operator
TreeNode *node = qt.front();
qt.pop();
// process null node
if (node == nullptr)
{
s.push_back('#');
s.push_back(',');
continue;
}
// process not null node
s += to_string(node->val);
s.push_back(',');
// push operator
qt.push(node->left);
qt.push(node->right);
}
char *ret = new char[s.length() + 1];
strcpy(ret, s.c_str());
return ret;
}
反序列化就是根据层次遍历在走一遍即可。 代码如下：
TreeNode* Deserialize(char *str)
{
if (str == nullptr) {
return nullptr;
}
// 可用string成员函数
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;
}
所以，最终的代码是：
class Solution {
public:
char* Serialize(TreeNode *root)
{
string s;
queue<TreeNode*> qt;
qt.push(root);
while (!qt.empty())
{
// pop operator
TreeNode *node = qt.front();
qt.pop();
// process null node
if (node == nullptr)
{
s.push_back('#');
s.push_back(',');
continue;
}
// process not null node
s += to_string(node->val);
s.push_back(',');
// push operator
qt.push(node->left);
qt.push(node->right);
}
char *ret = new char[s.length() + 1];
strcpy(ret, s.c_str());
return ret;
}
TreeNode* Deserialize(char *str)
{
if (str == nullptr) {
return nullptr;
}
// 可用string成员函数
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;
}
};
此题主要考察对树的遍历和构造树。</treenode*></treenode*></treenode*>
京公网安备 11010502036488号