题解 | #序列化二叉树#

#include <string>
#include <vector>
class Solution {
public:
    std::string str;
    
    char* Serialize(TreeNode *root) {
        if (!root) return nullptr;
        
        auto currentLevel = new vector<TreeNode *>();
        currentLevel->push_back(root);

        stringstream  res;

        while(!currentLevel->empty()){
            auto nextLevel = new vector<TreeNode *>();
            for(auto node: *currentLevel) {
                int val = node->val;
                if (node->left) {
                    nextLevel->push_back(node->left);
                    val |= 0xff << 24;
                }
                if (node->right) {
                    nextLevel->push_back(node->right);
                    val |= 0xff << 16;
                }
                res << val << ",";
            }
            if (nextLevel->empty()) break;
            currentLevel = nextLevel;
        }
        str.clear();
        str.append(res.str());
        // std::cout << str;
        return const_cast<char*>(str.c_str());
    }

    TreeNode* Deserialize(char *str) {
        if (!str) return nullptr;
        vector<int> values;

        std::string original(str);
        
        size_t pos = 0;
        while((pos = original.find(",")) != std::string::npos) {
            auto val = original.substr(0, pos);
            original = original.substr(pos + 1);
            values.push_back(atoi(val.c_str()));
        }
        if (values.empty()) return nullptr;

        auto currentLevel = new vector<TreeNode*>();

        auto root = new TreeNode(0);
        currentLevel->push_back(root);
        
        

        int i= 0;
        size_t values_size = values.size();

        while (!currentLevel->empty()) {
            auto nextLevel = new vector<TreeNode*>();
            for (auto node: *currentLevel) {
                if (i >= values_size) return root;
                int val = values[i++];
                node->val = val & 0xff;

                if ((val >> 24) & 0xff) {
                    node->left = new TreeNode(0);
                    nextLevel->push_back(node->left);
                }
                if ((val >> 16) & 0xff) {
                    node->right = new TreeNode(0);
                    nextLevel->push_back(node->right);
                }
            }
            if (nextLevel->empty()) break;
            currentLevel = nextLevel;
        }
        return root;
    }

};

题目事先说明: 每个节点 val 在 [0, 150] 之内, 因此 8 位足够存 val 的值

为了避免浪费 32 位的 int, 我们可以划分一下空间

`| 8位，记录是否存在左子树 | 8位，记录是否存在右子树 | 8位，闲置 | 8位，记录 val 值 |`

然后，我们就可以在层次遍历的时候，忽略不存在的节点（不需要使用 # 补位），进而可以实现更高效的 序列化与反序列化。

---

进一步，因 char 是 8位， 我们可以使用 2 个 char 来记录一个节点，下次发。