LC 297 Serialize and Deserialize Binary Tree

问题： Serialize and Deserialize Binary Tree

描述：

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

 

答案:

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Codec {
11 public:
12 
13     // Encodes a tree to a single string.
14     string serialize(TreeNode* root) {
15         if(root == NULL){
16             return "#";
17         }
18         return to_string(root->val) + ","+serialize(root->left)+","+serialize(root->right);
19     }
20 
21     // Decodes your encoded data to tree.
22     TreeNode* deserialize(string data) {
23         if(data == "#")return NULL;
24         stringstream s(data);
25         return helper(s);
26     }
27     
28     TreeNode* helper(stringstream& s){
29         string temp;
30         getline(s,temp,',');
31         
32         if(temp == "#"){
33             return NULL;
34         }else{
35             TreeNode* root = new TreeNode(stoi(temp));
36             root->left = helper(s);
37             root->right= helper(s);
38             
39             //stoi(str, 0, n); //将字符串 str 从 0 位置开始到末尾的 n 进制转换为十进制
40 
41             
42             return root;
43         }
44     }
45 
46 };
47 
48 // Your Codec object will be instantiated and called as such:
49 // Codec codec;
50 // codec.deserialize(codec.serialize(root));

说明：

stringstream

是 C++ 提供的另一个字串型的串流(stream)物件，和 iostream、fstream 有类似的操作方式。要使用 stringstream， 必須先加入這一行：#include <sstream>。

第28行，使用 stringstream s(data) 将string类型的data转换为 stringstream类型的s，传递到helper函数里。问题是，既然我们要的是string，那么为什么不直接转换？其实目的是为了分割，原来的string是类似的格式 ”1，2，3，NULL，NULL，4“，所有的数字都是通过逗号隔开，如果要在c++中进行拆分，那么进行转化比较方便。

转化过后，使用 getline(s,temp,','); 。 以 逗号 为分界，将第一个逗号之前的内容，存入temp。

stoi

然后，你可以看到stoi函数。功能是：将 n 进制的字符串转化为十进制。

int a = stoi(str, 0, 2);
/*
0是从0位开始
2是2进制
默认是10进制，所以这道题目直接填入string 数字就好
return是int型
*/

再谈 string 和 char

在其它的地方曾看到 string 和 char 的对比，比较直观清晰，就贴在这里作为记录。

操作	string	char列表
初始化	string s;	char s[100];
获取第i个字节	s[i]	s[i]
字符串长度	s.length() or s.size()	strlen(s)
读取一行	getline(cin,s)	gets(s)
设定某一行	s = "KYK"	strcpy(s,"KYK")
字符串相加	s = s+ "KYK"; s += "KYK"	strcat(s,"KYK")
字符串比较	s == "KYK"	strcmp(s,"KYK")

出处：https://www.twblogs.net/a/5b80fc902b71772165aa71f4

原文链接:https://www.cnblogs.com/kykai/p/11408231.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有