题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
private:
    char sep = ',';
    char null_node = '#';
public:
    char* Serialize(TreeNode *root) {    
        if(root == nullptr){
            return nullptr;
        }
        
        queue<TreeNode*> Q;
        Q.push(root);
        string res = "";
        while(!Q.empty()){
            auto node = Q.front();
            Q.pop();
            if(node){
                res += to_string(node->val);
                Q.push(node->left);
                Q.push(node->right);
            }
            else{
                res.push_back(null_node);
            }
            res.push_back(sep);
        }
        char* a = new char[res.length()+1];
        strcpy(a, res.c_str());
        return a;
    }
    
    TreeNode* Deserialize(char *str) {
        if(str == nullptr){
            return nullptr;
        }
        
        string res(str);
        if(res[0] == null_node){
            return nullptr;
        }
        
        vector<string> nodes = split_string(res, ",");
        
        queue<TreeNode*> Q;
        TreeNode* root = new TreeNode(stoi(nodes[0]));
        Q.push(root);
        
        for(int i=1; i<nodes.size();){
            auto parent = Q.front();
            Q.pop();
            string left = nodes[i++];
            if(left != "#"){
                parent->left = new TreeNode(stoi(left));
                Q.push(parent->left);
            }
            else{
                parent->left = nullptr;
            }
            
            string right = nodes[i++];
            if(right != "#"){
                parent->right = new TreeNode(stoi(right));
                Q.push(parent->right);
            }
            else{
                parent->right = nullptr;
            }
        }
        
        return root;
    }
    
    vector<string> split_string(string s, string pattern) {
        vector<string> res;
        // s += pattern;
        int pos;
        for (int i = 0; i < s.length(); i++) {
            pos = s.find(pattern, i);
            if (pos < s.length()) {
                string temp = s.substr(i, pos - i);
                res.push_back(temp);
                i = pos + pattern.length() - 1;
            }
        }
        return res;
    }
};