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")

出处：