题解 | #序列化二叉树#

class Solution {
  public:
    char* Serialize(TreeNode* root) {
        queue<TreeNode*> nodes;
        nodes.push(root);
        string ret;
        while (!nodes.empty()) {
            auto cur_node = nodes.front();
            nodes.pop();
            if (cur_node == nullptr)
                ret += "#,";
            else {
                ret += to_string(cur_node->val);
                ret += ',';
                nodes.push(cur_node->left);
                nodes.push(cur_node->right);
            }
        }
        char* result = strdup(ret.c_str());
        return result;
    }
    TreeNode* Deserialize(char* str) {
        if ((str == nullptr) || (*str == '\0'))
            return nullptr;
        string orig = str;
        queue<string> backlog;
        queue<TreeNode**> tree;
        const char delimiter = ',';
        ssize_t pos;
        while ((pos = orig.find(delimiter)) != string::npos) {
            backlog.push(orig.substr(0, pos));
            orig.erase(0, pos + 1);
        }
        auto head = stonode(backlog.front());
        backlog.pop();
        if (head != nullptr) {
            tree.push(&(head->left));
            tree.push(&(head->right));
        }
        while (!backlog.empty()) {
            auto cur_node = tree.front();
            tree.pop();
            *cur_node = stonode(backlog.front());
            backlog.pop();
            if ((*cur_node) != nullptr) {
                tree.push(&((*cur_node)->left));
                tree.push(&((*cur_node)->right));
            }
        }
        return head;
    }
  private:
    TreeNode* stonode(const string& str) {
        if (str.compare("#") == 0)
            return nullptr;
        else
            return new TreeNode(stoi(str));
    }
};