题解 | #JZ37 序列化二叉树#

//层序遍历
/*
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) {    
        vector<TreeNode*> curLvNodes, nextLvNodes;
        string str;
        
        if (root) curLvNodes.push_back(root);
        while (curLvNodes.size()) {
            int flg = 0;    //下一层不全为空标志
            for (int i=0; i!=curLvNodes.size(); ++i) {
                if (str.size()) str += ",";
                if (curLvNodes[i]) {
                    str += to_string(curLvNodes[i]->val);
                    nextLvNodes.push_back(curLvNodes[i]->left);
                    nextLvNodes.push_back(curLvNodes[i]->right);
                    if (curLvNodes[i]->left || curLvNodes[i]->right) flg = 1;
                } else {
                    str += "#";
                }
            }
            if (flg == 0) nextLvNodes.clear();    //下一层无有效节点，则清除
            curLvNodes.clear();
            curLvNodes.swap(nextLvNodes);
        }
        
        return strdup(str.c_str());
    }
    TreeNode* Deserialize(char *str) {
        char *p = str;
        TreeNode *root=nullptr;
        vector<TreeNode*> nodeVec;
        int pos = 0;
        
        if (!str || strlen(str)==0) return nullptr;
        
        while (p) {
            if (root == nullptr) {
                root = new TreeNode(atoi(p));
                nodeVec.push_back(root);
            } else {
                if (*p != '#') {
                    nodeVec[pos]->left = new TreeNode(atoi(p));
                    nodeVec.push_back(nodeVec[pos]->left);
                }
                p = strchr(p, ',') + 1;
                if (*p != '#') {
                    nodeVec[pos]->right = new TreeNode(atoi(p));
                    nodeVec.push_back(nodeVec[pos]->right);
                }
                ++pos;
            }
            
            p = strchr(p, ',');
            if (p) p += 1;
        }
        
        return root;
    }
};