题意

实现序列化和反序列化二叉树

solution

法一：层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string nullStr = "null";
    queue<TreeNode*> q;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL)return nullStr;
        q.push(root);
        string res = "";
        res += to_string(root->val);
        res += " ";
        while(!q.empty()){
            TreeNode* frt = q.front();
            q.pop();
            if(frt->left != NULL){
                q.push(frt->left);
                res += to_string(frt->left->val);
            }else{
                res += nullStr;
            }
            res += " ";
            if(frt->right != NULL){
                q.push(frt->right);
                res += to_string(frt->right->val);
            }else {
                res += nullStr;
            }
            res += " ";
        }
        //cout << res << endl;
        return res.substr(0, res.size()-1);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == nullStr)return NULL;
        stringstream ss;
        ss << data;
        vector<string> str;
        string val;
        while(ss >> val){
            str.push_back(val);
        }
        TreeNode* root = new TreeNode(stoi(str[0]));
        int i = 1;
        q.push(root);

        /*for(string s : str){
            cout << s << endl;
        }*/

        while(!q.empty()){
            TreeNode* frt = q.front();
            q.pop();
            if(str[i] != nullStr){
                TreeNode* p = new TreeNode(stoi(str[i]));
                frt->left = p;
                q.push(p);
            }
            i ++;
            if(str[i] != nullStr){
                TreeNode* p = new TreeNode(stoi(str[i]));
                frt->right = p;
                q.push(p);
            }
            i ++;
        }

        return root;
    }
};

法二：
前序遍历，递归的解法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res = "";
        dfs_s(root, res);
        return res.substr(0, res.size()-1);
    }

    void dfs_s(TreeNode* root, string& res){
        if(root == NULL){
            res += "null ";
            return;
        }

        res += to_string(root->val) + " ";
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss << data;
        string val;
        vector<string> str;
        while(ss >> val){
            str.push_back(val);
        }

        int i = 0;
        return dfs_d(str, i);
    }

    TreeNode* dfs_d(vector<string>& data, int &i){
        if(i == data.size())return NULL;

        if(data[i] == "null"){
            i ++;
            return NULL;
        }
        TreeNode* root = new TreeNode(stoi(data[i]));
        i ++;
        root->left = dfs_d(data, i);
        root->right = dfs_d(data, i);

        return root;
    }
};