问题：

实现下面两个转换：

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（二叉树）

先序遍历

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

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

♻️ 优化：

这里，

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

特点：

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

代码参考：

• 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 };

 

• 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 };