题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
  public:
    char* Serialize(TreeNode* root) {
        queue<TreeNode*> treeList;
        treeList.push(root);
        string s = "";

        function<char* (string)> StringToCharStar = [&](string mystr) {
            char* mychar = new char[mystr.size() + 1];
            copy(mystr.begin(), mystr.end(), mychar);
            mychar[mystr.size()] = '\0';
            return mychar;
        };

        while (!treeList.empty()) {
            int n = treeList.size();
            for (int i = 0; i < n; i++) {
                auto p = treeList.front();
                treeList.pop();
                if (p) {
                    s += to_string(p->val) + ' ';
                    treeList.push(p->left);
                    treeList.push(p->right);
                } else {
                    s += "# ";
                }
            }
        }
        return StringToCharStar(s);
    }

    TreeNode* Deserialize(char* str) {
        string s = "";
        queue<TreeNode*> treeVec;
        while (*str != '\0') {
            char cc = *str;
            if (cc == '#') {
                treeVec.push(NULL);
            } else if (isdigit(cc)) {
                s += cc;
            } else if (cc == ' ') {
                if (s != "") {
                    TreeNode* pp = new TreeNode(stoi(s));
                    treeVec.push(pp);
                    s = "";
                }
            }
            str++;
        }
        if (treeVec.size() <= 0)
            return NULL;
        int n = treeVec.size();
        TreeNode* root = treeVec.front();
        treeVec.pop();
        queue<TreeNode*> treeList;
        treeList.push(root);
        while (!treeVec.empty()) {
            auto pR = treeList.front();
            treeList.pop();
            if (!pR)
                continue;
            auto leftR = treeVec.front();
            treeVec.pop();
            auto rightR = treeVec.front();
            treeVec.pop();
            pR->left = leftR;
            pR->right = rightR;
            treeList.push(pR->left);
            treeList.push(pR->right);
        }
        return root;
    }
};