题解 | #序列化二叉树#一种效率较低的方法，利用二叉树顺序存储

我们知道二叉树有一种存储方法是顺序存储，在这种存储下面，第i个结点的左右孩子分别是2i和2i+1。如果用这个方法存储二叉树，则其反序列化的思路会变得非常简单。但这种方法其实效率较低，因为如果我们要实现顺序存储，意味着在处理空结点时也要像有数据的结点一样把它的左右孩子入队。

效率低的原因是：第一，空结点的孩子也要入队；第二，构造树的过程中需要很多判断分支来考虑是否为空。

其过程是，首先用层次遍历序列化，在序列过程中，即使遇到nullptr也要将其左右孩子入队（即入2个nullptr），据此构建一个完整的顺序结构（但为了简化判断条件，如果最后几个叶子结点均为空，就不继续序列化了）。比如说有一棵树其结构为[1,2,#,3,#,#,#,4,5,#,#,#,#,#,#]（即：树根1，第二层2,#，第三层3,#,#,#，叶子4,5,#,#,#,#,#,#），那么我们实际上将其构造成1,2,#,3,#,4,5,的序列就足够我们进行序列与反序列化。但在现在这个做法里面，将其序列成1,2,#,3,#,#,#,4,5,；然后在反序列化中，将其所有结点全部构造出来，然后根据在顺序存储结构中第i个结点的左右孩子分别是2i和2i+1构造这棵树。

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(root==nullptr){
            return "#,";
        }
        string res;
        size_t nullCount=0;
        queue<TreeNode*> qu;
        qu.push(root);
        while(qu.size()!=nullCount){
            TreeNode *p=qu.front();
            res+=visitNodeStr(p);
            qu.pop();
            if(p!=nullptr){
                qu.push(p->left);
                qu.push(p->right);
                if(p->left==nullptr)nullCount++;
                if(p->right==nullptr)nullCount++;
            }
            else{
                qu.push(nullptr);
                qu.push(nullptr);
                nullCount++;
            }
        }
        char *ret = new char[res.length() + 2];
        int i=0;
        for(;i<res.length();i++)
            ret[i]=res[i];
        ret[i]='\0';
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        if (str == nullptr) {
            return nullptr;
        }
        string s(str);
        if (str[0] == '#') {
            return nullptr;
        }
        vector<TreeNode*> v;
        TreeNode *ret = new TreeNode(atoi(s.c_str()));
        v.push_back(ret);
        s = s.substr(s.find_first_of(',') + 1);
        while(!s.empty()){
            if(s[0]=='#'){
                v.push_back(nullptr);
                s = s.substr(2);
            }
            else{
                TreeNode *n=new TreeNode(atoi(s.c_str()));
                v.push_back(n);
                s = s.substr(s.find_first_of(',') + 1);
            }
        }
        size_t i=0,sz=v.size();
        while((i+1)*2-1<sz){
            if(v[i]==nullptr){i++;continue;}
            v[i]->left=v[(i+1)*2-1];
            v[i]->right=v[(i+1)*2];
            i++;
        }
        return v[0];
    }
    string visitNodeStr(TreeNode* p){
        if(p==nullptr)return "#,";
        else return to_string(p->val)+",";
    }
};