二叉树的序列化和反序列化

• 序列化：将数据结构转换成字符串或字节流的过程，便于存储或传输。
• 反序列化：将字符串或字节流转换回原始数据结构的过程。

二叉树的序列化

二叉树的序列化可以采用两种思路：DFS （深度优先搜索）和BFS（广度优先搜索）。下面给出实现：

BFS

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string retStr = "";
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int s = que.size();
            for(int i = 0;i < s;i++){
                TreeNode* curNode = que.front();
                if(!curNode){
                    retStr +="# ";
                }else{
                    retStr += to_string(curNode->val);
                    retStr +=" ";
                    que.push(curNode->left);
                    que.push(curNode->right);
                }
                que.pop();
            }
        }
        return retStr;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        string temp = "";
        TreeNode* root = nullptr;
        queue<TreeNode**> que;
        que.push(&root);
        while(iss >> temp){
            if(temp == "#"){
                que.pop();
            }else{
                *que.front() = new TreeNode(stoi(temp));
                que.push(&((*que.front())->left));
                que.push(&((*que.front())->right));
                que.pop();
            }
        }
        return root;
    }
};

DFS

class Codec {
public:
    void rserialize(TreeNode* root, string& str) {
        if (root == nullptr) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    string serialize(TreeNode* root) {
        string ret;
        rserialize(root, ret);
        return ret;
    }

    TreeNode* rdeserialize(list<string>& dataArray) {
        if (dataArray.front() == "None") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    }

    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string str;
        for (auto& ch : data) {
            if (ch == ',') {
                dataArray.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        if (!str.empty()) {
            dataArray.push_back(str);
            str.clear();
        }
        return rdeserialize(dataArray);
    }
};