题解 | #序列化二叉树#

#include <string>
#include <vector>
class Solution {
  public:
    char gstr[512];

    char* Serialize(TreeNode* root) {
        if (!root) return nullptr;
        // 准备层次遍历
        auto currentLevel = new vector<TreeNode*>();
        currentLevel->push_back(root);
        // 计数
        int count = 0;
        // 开始层次遍历
        while (!currentLevel->empty()) {
            auto nextLevel = new vector<TreeNode*>();
            for (auto node : *currentLevel) {
                // 将节点值记录到 char 中
                char val = node->val - 128;
                // 将左右子节点情况，记录到另一个 char 中
                char offset = 1;
                if (node->left) {
                    nextLevel->push_back(node->left);
                    offset |= 0xf0;
                }
                if (node->right) {
                    nextLevel->push_back(node->right);
                    offset |= 0x0f;
                }
                // 写入 gstr
                gstr[count++] = val;
                gstr[count++] = offset;
            }
            if (nextLevel->empty()) break;
            currentLevel = nextLevel;
        }
        gstr[count] = '\0';
        return gstr;
    }

    TreeNode* Deserialize(char* str) {
        if (!str) return nullptr;

        auto currentLevel = new vector<TreeNode*>();
        // 构建根节点
        auto root = new TreeNode(0);// 节点值不用管，后面会设置
        currentLevel->push_back(root);
        char* p = str;

        while (!currentLevel->empty()) {
            auto nextLevel = new vector<TreeNode*>();
            for (auto node : *currentLevel) {
                if (!p) return root;
                // 读出节点值
                int val = 128 + (int) (*p); 
                p++;
                // 读出 左右子树情况
                if (!p || *p == '\0') return root;
                int hasLeft = (0xf0 & (*p)) == 0xf0;
                int hasRight = (0x0f & (*p)) == 0x0f;
                p++;
                // 赋节点值
                node->val = val;
                // 如果有子树，先构造节点，等后面层次遍历到它的时候，再赋节点值
                if (hasLeft) {
                    node->left = new TreeNode(0);
                    nextLevel->push_back(node->left);
                }
                if (hasRight) {
                    node->right = new TreeNode(0);
                    nextLevel->push_back(node->right);
                }
            }
            if (nextLevel->empty()) break;
            currentLevel = nextLevel;
        }
        return root;
    }
};

https://www.nowcoder.com/discuss/457330487380480000