剑指37题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
/*
	遵循思想，通俗易解
    层序遍历，空格用#字符
    层序遍历时，有#表示空格时，不需要添加换行标记，因为遵循层序遍历时，一个节点会读两个子节点规律的，对于空的，使用#表示
    编码时，使用了Vector容器标记每层的子节点存在情况，对于都为空时，那么不再填充#
    编解码时，均采用数字记录器来表示空节点，目的方便判断
*/
#include <algorithm>
#include <cstring>
#include <limits>
#include <queue>
#include <sstream>
#include <string>
#include <vector>
class Solution {
public:
    // char* c;
    char* Serialize(TreeNode *root) {
        if(!root) return nullptr;    
        string s;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> v;      // 记录器，记录每一层的节点非空情况
        v.push_back(1);     // 记录root节点层存在非空节点
        TreeNode* tmp_node = new TreeNode(151);     // 自定义一个假节点，方便处理空节点（补充说明，一开始采用整体返回数值字符串，奈何一直超过内存限制，解码会失败，所以假节点还是在字符串中表示为#）
        while (!q.empty()) {
            bool flag = count(v.begin(), v.end(), 1);   // 目的确保下一层中存在非空子节点
            v.clear();  // 下一层时，需要重置记录器
            int num = q.size(); // 记录当前层含假节点（空节点）在内的节点数目
            // 开始层序遍历
            for(int i = 0; i < num; ++i)
            {
                TreeNode* tmp = q.front();
                q.pop();
                if(flag){
                    if(tmp->val != 151){    // 非假（空）节点时，直接入string容器
                        s.append(to_string(tmp->val) + ',');
                    }
                    else{
                        s.append("#,");     // 空
                    }
                }
                if(tmp->left){  // 左子节点存在时
                    q.push(tmp->left);  // 入队
                    v.push_back(1);     // 记录当前层中的子节点存在
                }
                else if(tmp->val != 151){
                    q.push(tmp_node);   // 对于空节点，这里给个假节点作为标记，不然后面没法加入 #
                    v.push_back(0);     // 记录子节点为空
                }
                if(tmp->right)          // 意义同上
                {
                    q.push(tmp->right);
                    v.push_back(1);
                }
                else if(tmp->val != 151){
                    q.push(tmp_node);
                    v.push_back(0);
                }
            }
        }
        // char* c = (char*) s.data();          // 这种写法会导致解码时拿到是一个空字符串
        char* res = new char(s.length()+1);     // 需要给返回指针开辟一个空间，否则反解析无法接收字符串
        strcpy(res, s.c_str());                 // 注意字符串后面会有一个 ‘\0’ 结尾，所以开辟空间时，得+1
        // std::cout << " 编码： " << s << std::endl;
        return res;
    }

    int getVal(string s, int& k)    // 获取数值，对于#字符，返回-1
    {
        int val = 0;
        if(s[k] == '#') k+=1;
        for(; k < s.size()&& s[k] != ','; ++k)
        {
            val = val * 10 + (s[k] - '0');  // int类型跟字符转换就是差个 '0' 
        }
        return val==0?-1:val;
    }
    TreeNode* Deserialize(char *str) {
        if(!str) return nullptr;
        string s = str;
        // std::cout << s << std::endl; // 注意字符串包含了 数字字符、#、 , 三者
        int val = 0;
        int k = 0;
        val = getVal(s, k);
        k += 1;
        TreeNode* root = new TreeNode(val);
        queue<TreeNode*> q;
        q.push(root);
        // 层序遍历解码重建树
        while (!q.empty() && k < s.size()) {
            int num = q.size();
            for(int j = 0; j < num ;++j)
            {
                TreeNode* cur = q.front();
                q.pop();
                val = getVal(s, k);
                if (val != -1) {
                    cur->left = new TreeNode(val);
                    q.push(cur->left);
                }
                val = getVal(s, ++k);
                if(val != -1){
                    cur->right = new TreeNode(val);
                    q.push(cur->right);
                }
                ++k;
            }
        }
        return root;
    }
};