//二叉树的先序遍历-序列化

#include <iostream>

#include <string>

#include <sstream>

using namespace std;

struct TreeNode {

    int val;

    TreeNode* left;

    TreeNode* right;

    TreeNode(int x) :val(x), left(NULL), right(NULL) {} //构造函数

};

class Solution {

public:

    string treeToStr(TreeNode* head) {

        if (head == NULL) {

            return "#_";

        }

        string res = int2str(head->val) + "_";

        res += treeToStr(head->left);

        res += treeToStr(head->right);

        return res;

    }

    //int to string

    string int2str(const int &int_temp)

    {

        stringstream stream;

        stream << int_temp;

        string string_temp = stream.str();   //此处也可以用 stream>>string_temp

        return string_temp;

    }

};

int main() {

    //生成一棵二叉树

    TreeNode* head = new TreeNode();

    head->left = new TreeNode();

    head->right = new TreeNode();

    head->left->right = new TreeNode();

    head->right->left = new TreeNode();

    Solution test;

    string s = test.treeToStr(head);

    for (auto c : s) {

        cout << c;

    }

    cout << endl;

    return 0;

class Solution {

public:

    TreeNode* strToTree(string s) {

        //判空

        int sz = s.size();

        if (sz == ) return NULL;

        //先序遍历，借助栈

        stack<TreeNode*> stack;

        int idx = ;

        TreeNode* head = new TreeNode((c2i(s[idx])));

        idx = idx + ;//跳过‘_’分隔符

        TreeNode* cur = head;

        while ((cur || !stack.empty() )&& idx<sz) {

            //借助栈，先序遍历

            if (cur) {

                stack.push(cur);

                cur->left = gNode(s[idx]);

                idx += ;//跳过‘_’分隔符

                cur = cur->left;

            }

            else {

                cur = stack.top();

                cur->right = gNode(s[idx]);

                idx += ;

                stack.pop();

                cur = cur->right;

            }

        }

        return head;

    }

    //generate TreeNode

    TreeNode* gNode(char a) {

        if (a == '#')

            return NULL;

        else {

            return new TreeNode(c2i((a)));

        }

    }

   //char to int

    int c2i(const char &char_temp)

    {

        stringstream stream;

        stream << char_temp;

        int int_temp;

        stream >> int_temp;

        return int_temp;

    }

};

//二叉树的反序列化-先序遍历

#include <iostream>

#include <string>

#include <sstream>

#include <stack>

using namespace std;

struct TreeNode {

    int val;

    TreeNode* left;

    TreeNode* right;

    TreeNode(int x) :val(x), left(NULL), right(NULL) {} //构造函数

};

class Solution1{

public:

    string serial_Of_Tree(TreeNode* head) {

        if (head == NULL) {

            return "#_";

        }

        string res = int2str(head->val) + "_";

        res += serial_Of_Tree(head->left);

        res += serial_Of_Tree(head->right);

        return res;

    }

    //int to string

    string int2str(const int &int_temp)

    {

        stringstream stream;

        stream << int_temp;

        string string_temp = stream.str();   //此处也可以用 stream>>string_temp

        return string_temp;

    }

};

class Solution {

public:

    TreeNode* strToTree(string s) {

        //判空

        int sz = s.size();

        if (sz == ) return NULL;

        //

        stack<TreeNode*> stack;

        int idx = ;

        TreeNode* head = new TreeNode((c2i(s[idx])));

        idx = idx + ;

        TreeNode* cur = head;

        while ((cur || !stack.empty() )&& idx<sz) {

            if (cur) {

                stack.push(cur);

                cur->left = gNode(s[idx]);

                idx += ;

                cur = cur->left;

            }

            else {

                cur = stack.top();

                cur->right = gNode(s[idx]);

                idx += ;

                stack.pop();

                cur = cur->right;

            }

        }

        return head;

    }

    //generate TreeNode

    TreeNode* gNode(char a) {

        if (a == '#')

            return NULL;

        else {

            return new TreeNode(c2i((a)));

        }

    }

   //char to int

    int c2i(const char &char_temp)

    {

        stringstream stream;

        stream << char_temp;//stream作为中转站，另外使用<<和>>

        int int_temp;

        stream >> int_temp;

        return int_temp;

    }

};

int main() {

    string s = "3_1_#_2_#_#_5_4_#_#_#_";

    Solution test1;

    TreeNode* t= test1.strToTree(s);

    Solution1 test;

    string s2 = test.serial_Of_Tree(test1.strToTree(s));

    for (auto a : s2) {

        cout << a;

    }

    cout << endl;

    return ;

}