【二叉树序列化&反序列化】297. Serialize and Deserialize Binary Tree

问题：

实现下面两个转换：

TreeNode* -> string

string -> TreeNode*

Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [1]
Output: [1]

Example 4:
Input: root = [1,2]
Output: [1,2]
 
Constraints:
The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

解法：Binary Tree（二叉树）

方法一：preorder (先序遍历)（递归）

⚠️ 注意：构建二叉树，一般需要先序+中序 or 后序+中序三种遍历方法的其中两种，才能构建。

特别的，如果给出了叶子节点的null状况，则可由三种遍历方法的任意一种，构建。

♻️ 优化：

这里，

c++没有字符串分割函数split，我们利用输入输出流进行替代。

特点：

TreeNode* -> string
- ostringstream out << val
  - ostringstream -> string 方法： out.str()
string -> TreeNode*
- istringstream in >> val
  - 默认使用空格，进行分割读取。
  - string -> istringstream 构造方法：in(string data)

代码参考：

TreeNode* -> string
- ostringstream out << val
  - ostringstream -> string 方法： out.str()

 1 class Codec {
 2 public://Preorder
 3     string NUL = "#";
 4     string SEP = " ";
 5 
 6     // Encodes a tree to a single string.
 7     string serialize(TreeNode* root) {
 8         ostringstream code;
 9         serialize_code(root, code);
10         return code.str();
11     }
12     void serialize_code(TreeNode* root, ostringstream& code) {
13         if(!root) {
14             code << NUL << SEP;
15             return;
16         }
17         //root
18         code << root->val << SEP;
19         //child
20         serialize_code(root->left, code);
21         serialize_code(root->right, code);
22     }
23 };

string -> TreeNode*
- istringstream in >> val
  - 默认使用空格，进行分割读取。
  - string -> istringstream 构造方法：in(string data)

 1 class Codec {
 2 public://Preorder
 3     string NUL = "#";
 4     string SEP = " ";
 5 
 6     // Decodes your encoded data to tree.
 7     TreeNode* deserialize(string data) {
 8         istringstream code(data);
 9         return deserialize_code(code);
10     }
11     TreeNode* deserialize_code(istringstream& code) {
12         string val;
13         code >> val;
14         if(val == NUL) return nullptr;
15 
16         TreeNode* root = new TreeNode(stoi(val));
17         root->left = deserialize_code(code);
18         root->right = deserialize_code(code);
19         return root;
20     }
21 };

方法二：BFS (层序遍历，广度优先搜索)（循环）

主要思想：

使用queue对TreeNode进行保存，

处理node，弹出node，pop(node)

得到node->left, node->right，并入队push(node->left), push(node->right)

代码参考：

TreeNode* -> string
- ostringstream out << val

 1 class Codec {
 2 public://BFS
 3     string NUL = "#";
 4     string SEP = " ";
 5 
 6     // Encodes a tree to a single string.
 7     string serialize(TreeNode* root) {
 8         if(!root) return NUL;
 9         queue<TreeNode*> q; //queue
10         ostringstream out;
11         q.push(root);
12         while(!q.empty()) {
13             TreeNode* node = q.front();
14             q.pop();
15             if(!node) out << NUL << SEP;
16             else {
17                 out << node->val << SEP;
18                 q.push(node->left);
19                 q.push(node->right);
20             }
21         }
22         return out.str();
23     }
24 };

string -> TreeNode*
- istringstream in >> val

class Codec {
public://BFS
    string NUL = "#";
    string SEP = " ";

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        queue<TreeNode*> q;  //queue
        TreeNode* root;
        string val;
        in >> val;
        if(val==NUL) return nullptr;
        q.push(new TreeNode(stoi(val)));
        root = q.front();
        
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if(!node) continue;
            in >> val;
            if(val==NUL) node->left=nullptr;
            else node->left=new TreeNode(stoi(val));
            in >> val;
            if(val==NUL) node->right=nullptr;
            else node->right=new TreeNode(stoi(val));
            q.push(node->left);
            q.push(node->right);
        }
        
        return root;
    }
};

参考：stringstream 实现字符串分隔

stringstream默认分割空格、tab、回车换行

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     string s1, s2;
 6     s1 = "Those who cannot remember the past are condemned to repeat it";
 7     stringstream ss(s1);
 8     while(ss >> s2)
 9         cout << s2 << endl;
10 }
11 /*
12 输出：
13 Those
14 who
15 cannot
16 remember
17 the
18 past
19 are
20 condemned
21 to
22 repeat
23 it
24 */

利用指定字符分割字符串

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     string s1, s2;
 6     s1 = "Those*who*cannot*remember*the*past*are*condemned*to*repeat*it";
 7     stringstream ss(s1);
 8     while(getline(ss, s2, '*'))
 9         cout << s2 << endl;
10 }
11 /*
12 输出：
13 Those
14 who
15 cannot
16 remember
17 the
18 past
19 are
20 condemned
21 to
22 repeat
23 it
24 */