题解 | #序列化二叉树#
序列化二叉树
https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
先了解下这几个函数
- find_first_of()函数
正向查找在原字符串中第一个与指定字符串（或字符）中的某个字符匹配的字符，返回它的位置。若查找失败，则返回npos。（npos定义为保证大于任何有效下标的值。）
string str=“abcdefab”;
cout<<str.find_first_of(“hce”)<<endl;//待查串hce第一个出现在原串str中的字符是c，返回str中c的下标2,故结果为2。第二个参数为0，默认从原串下标为0开始正向查。
cout<<str.find_first_of(“ab”,1)<<endl;//从下标为1开始查，待查串ab第一个出现在原串str中的字符是b，返回b的下标，结果为1。 - atoi(const char* x);
将字符串转化为 int 类型,不会对转化后的数进行检查，超出上界，输出上界，超出下界，输出下界； - c_str()
将 const string* 类型 转化为 cons char* 类型
c_str() 这个函数转换后返回的是一个临时指针，不能对其进行操作,所以因为这个数据是临时的，所以当有一个改变这些数据的成员函数被调用后，该数据就会改变失效；如果想要保持需要使用strcpy()函数复制char ptr[5]; string s = "12345"; strcpy(ptr, s.c_str()); cout << "s改变前ptr为：" << ptr << endl; s = "66666"; cout << "s改变后ptr为：" << ptr << endl;
- substr()
substr（start, length）方法：返回一个从指定位置开始，并具有指定长度的子字符串。
参数：
1.start：必选。所需的子字符串的起始位置。字符串中第一个字符的索引为 0。
2.length：可选项。返回的子字符串中包含的字符数。
假设：string s = "0123456789";
string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789"
string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"
- to_string()
将数字常量（int,double,long等）转换为字符串（string），返回转换好的字符串
int num = 123456789;
string s = to_string(num);
然后说回这道题，
W： 采用层序遍历实现，根节点首先入队，进入循环获取当前节点，判断是否为空，为空插入'#'并跳到下一个循环
否则继续添加对应节点的值和‘，’号，和层序遍历不同的是，空节点也需要进入队列
W：序列转换为二叉树，需要去实现利用层序遍历构建，依次读取字符数组，遇到'#'插入空节点，否则插入对应值，并
更新序列，返回头节点即可
N：new 堆区指针；
find_first_of，后加1到'号后面
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int iterator(TreeNode* root){
if(root==nullptr){
return 0;
}
int left = iterator(root->left);
int right=iterator(root->right);
return 1+max(left,right);
}
char* Serialize(TreeNode *root) {
string res;
int depth=iterator(root);
queue<TreeNode*> que;
// if(root==nullptr) return res.c_str(); 不可行
que.push(root);
while(!que.empty()){
int size=que.size();
for(int i=0; i<size; i++){
TreeNode* cur=que.front();
que.pop();
if(cur==nullptr){
res.push_back('#');//使用单个push_back()
res.push_back(',');
continue;//非常重要note
}
res+=to_string(cur->val);//note 使用to_string,数字有多个字符
res.push_back(',');
// if(cur->left) 空节点也放
que.push(cur->left);
// if(cur->right)
que.push(cur->right);
}
}
//note char <-string
char *res_char=new char[res.size()+1];
strcpy(res_char,res.c_str());
return res_char;
}
TreeNode* Deserialize(char *str) {
//note 对于* 判断nullptr
if(str==nullptr) return nullptr;
string s(str);//构造stirng 对象便于操作
if(str[0]=='#'){
return nullptr;
}
TreeNode* res=new TreeNode(atoi(s.c_str()));//char->int
queue<TreeNode*> que;
que.push(res);
s=s.substr(s.find_first_of(',')+1);//find_first_of寻找第一个节点 ,
while(!que.empty() && !s.empty()){
TreeNode* cur=que.front();
que.pop();
if(s[0]=='#'){
cur->left=nullptr;
s=s.substr(2);//', note 赋值s=
}
else{
cur->left= new TreeNode(atoi(s.c_str()));
que.push(cur->left);
s= s.substr(s.find_first_of(',')+1);
}
if(s[0]=='#'){
cur->right=nullptr;
s= s.substr(2);//',
}
else{
cur->right= new TreeNode(atoi(s.c_str()));
que.push(cur->right);
s= s.substr(s.find_first_of(',')+1);
}
}
return res;
}
};
ref
https://blog.csdn.net/YXXXYX/article/details/119957061?spm=1001.2014.3001.5502
https://blog.csdn.net/liuchuo/article/details/54599840
https://blog.csdn.net/qq_40968179/article/details/104375849
https://blog.csdn.net/baidu_34884208/article/details/88342844?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-0-88342844-blog-119955817.pc_relevant_multi_platform_whitelistv4&spm=1001.2101.3001.4242.1&utm_relevant_index=3