题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <cstddef>
#include <cstring>
class Solution {
  public:
    char* Serialize(TreeNode* root) {
        if (root == nullptr) return "#";
        deque<TreeNode*> deq;
        deq.push_back(root);
        string res;
        int i = 1, num_count = 0, num_null_prev = 0, num_null_cur = 0;
        //层序遍历，数字之间使用！间隔，nullptr用#表示，先构建一个deque列表
        while (!deq.empty()) {
            TreeNode* temp = deq.front();
            deq.pop_front();
            if (temp != nullptr) {
                num_count++;
                res += to_string(temp->val) + "!";
                deq.push_back(temp->left);
                deq.push_back(temp->right);
            } else {
                num_null_cur++;
                res += '#';
            }
            //判断是第几层，该层是否已经满了。
            //i表示第i层，判断是否满足2^(i-1)=上一层nullptr的个数*2+当前层数字个数+当前层nullptr的个数，满足时当前层满了
		  //之前都没有空结点
            if (num_null_prev == 0) {
			  //当前层满了
                if (num_count + num_null_cur == pow(2, i - 1)) {
                    i++;
				  //到下一层的时候需要更新数值
                    num_count = 0;
                    num_null_prev = num_null_cur;
                    num_null_cur = 0;
                }
            } else {
			  //当前层满了
                if (2 * num_null_prev + num_null_cur + num_count == pow(2, i - 1)) {
                    i++;
                    num_count = 0;
				  //前一层空结点个数 = 前一层空结点个数*2+当前层空结点个数
                    num_null_prev = num_null_cur + 2 * num_null_prev;
                    num_null_cur = 0;
                }
            }
        }
        //最后的叶结点添加了2个nullptr进入deque中，多算了一层；在公式中又多加了一层，所以是减2
        i -= 2;
        //！的位置为终点的位置，计算长度（长度为终点位置+1），char*数组需在长度的基础上再+1，因为要加终止符
        int pos = res.find_last_of('!');
        char* res_ptr = new char[pos + 2];
        res = res.substr(0, pos + 1);

        strcpy(res_ptr, res.c_str());
        res_ptr[pos + 1] = '\0';
        return res_ptr;
    }
    TreeNode* Deserialize(char* str) {
        if (str == nullptr) return nullptr;
        deque<TreeNode*> deq1, deq2;
        string val;
        //构建两个队列，第一个队列为父结点，第二个队列为子节点，第二个队列删去根结点。
        for (int i = 0; str[i] != '\0'; i++) {
            if (isdigit(str[i])) {
                val += str[i];
            } else if (str[i] == '!') {
                TreeNode* temp = new TreeNode(atoi(val.c_str()));
                deq1.push_back(temp);
                deq2.push_back(temp);
                val.clear();
            } else {
                deq1.push_back(nullptr);
                deq2.push_back(nullptr);
            }
        }
        deq2.pop_front();
        TreeNode* root = deq1.front(), *cur = root;

        //当取出一个非空父结点时，对应取出两个子节点；空的父结点跳过。当子节点的deque为空时，结束循环
        while (deq2.size() != 0) {
            cur = deq1.front();
            deq1.pop_front();
            if (cur != nullptr) {
                //判断子节点列表是否为空，空则跳出循环
                if (deq2.size() == 0) break;
                cur->left = deq2.front();
                deq2.pop_front();
                
                //判断子节点列表是否为空，空则跳出循环
                if (deq2.size() == 0) break;
                cur->right = deq2.front();
                deq2.pop_front();
            }
        }
        return root;
    }
};