题解 | #序列化二叉树# 层序遍历+详细注释

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <cstdio>
#include <cstring>
#include <vector>
class Solution {
  public:
    char* Serialize(TreeNode* root) {
        // 用string来方便地保存字符串
        string res;
        // 考虑树根为空的特殊情况
        if (root == nullptr) {
            return "#";
        }
        // 为层序遍历创建一个队列
        queue<TreeNode*> que;
        // 统计该层有多少个空指针
        que.push(root);
        int nul_num = 0;
        while (!que.empty() ) {
            int n = que.size();
            if (nul_num == n) {
                // 如果一层全为空，则直接可以结束循环去构建返回值
                break;
            } else {
                // 如果不全为空，则清空计数器，方便统计下一层的空指针的个数
                nul_num = 0;
            }

            for (int i = 0; i < n; i++) {
                TreeNode* tmp = que.front();
                que.pop();
                // 层序遍历的队列更新逻辑
                if (tmp == nullptr) {
                    // 由于层序遍历的逻辑，空指针必须加入到队列
                    que.push(nullptr);
                    que.push(nullptr);
                    // 更新计数器
                    nul_num += 2;
                } else {
                    que.push(tmp->left);
                    que.push(tmp->right);
                    // 更新计数器
                    if (tmp -> left == nullptr) nul_num++;
                    if (tmp -> right == nullptr) nul_num++;
                }

                // 处理字符串逻辑，这里的逗号特别重要，否则在反序列化的时候会难以区分10 和 1 0
                if (tmp == nullptr) {
                    res += "#,";
                } else {
                    res += to_string(tmp->val);
                    res += ",";
                }
            }
        }
        // 注意这里的代码，没怎么写过，这是针对 char* 返回值的对策
        char* charRes = new char[res.size() + 1];
        // 和C语言相关的返回字符串，记住相关函数
        strcpy(charRes, res.c_str());
        // 需要手动更改数组的最后一个值
        charRes[res.size()] = '\0';
        printf("%s",charRes);
        return charRes;

    }
    TreeNode* Deserialize(char* str) {
        int n = strlen(str);
        cout <<"n:" << n << endl;
        // 处理元素较小的特殊情况
        if (str[0] == '#') {
            return nullptr;
        }
        // 按照下标存储节点，方便后续操作
        vector<TreeNode*> help;
        // 统计每个节点对应的字符串，以 ',' 为分割
        string s;
        int loc = 0;
        // 遍历整个字符串，同时构造“节点数组”，方便后续操作
        while(loc < n){
            if(str[loc] != ','){
                s += str[loc];
            }else{
                if(s == "#"){
                    help.push_back(nullptr);
                    s.clear();
                }else{
                    help.push_back(new TreeNode(stoi(s)));
                    s.clear();
                }
            }
            loc++;
        }
        // 组成树，这里的左右指针方式由层序遍历的逻辑决定。
        for (int i = 0; i < help.size(); i++) {
            if (help[i] != nullptr) {
                if (2 * i + 2 < help.size()) {
                    help[i] -> left = help[2 * i + 1];
                    help[i] -> right = help[2 * i + 2];
                } else {
                    help[i] -> left = nullptr;
                    help[i] -> right = nullptr;
                }
            }
        }
        return help[0];
    }
};