题解 | #序列化二叉树#

广度优先遍历

/*
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) {   
        string str;
        queue<TreeNode*> treeQueue;
        treeQueue.push(root);
        while(!treeQueue.empty())
        {
            int num=treeQueue.size();
            for(int i=0;i<num;++i)
            {
                TreeNode* temNode=treeQueue.front();
                treeQueue.pop();
                if(temNode)
                {
                    str+=to_string(temNode->val);
            
                    treeQueue.push(temNode->left);
                    treeQueue.push(temNode->right);
                }
                else
                {
                    str+=('#');
                    
                }
                 str+=" ";
            }
        }
        str.pop_back();
        char* ret=new char[str.size()+1];
        strcpy(ret, str.c_str());
        ret[str.size()]='\0';
        return ret;
        
    }
    TreeNode* Deserialize(char *str) {
        string mStr=str;

        stringstream mStream(mStr);
        vector<string> stringVector;
        string temString;
        while(mStream>>temString)
        {
            stringVector.push_back(temString);
        }
        

//         return nullptr;
        

        vector<TreeNode*> nodeVector(stringVector.size());
        for(int i=0;i<nodeVector.size();++i)
        {
            nodeVector[i]=stringVector[i]=="#"?nullptr:new TreeNode(stoi(stringVector[i]));
        }
        
        queue<TreeNode*> treeQueue;
        treeQueue.push(nodeVector[0]);
        int index=0;
        while(!treeQueue.empty())
        {
            int num=treeQueue.size();
            for(int i=0;i<num;++i)
            {
                TreeNode* temNode=treeQueue.front();
                treeQueue.pop();
                if(temNode)
                {
                    index++;

                    temNode->left=nodeVector[index];
                    index++;

                    temNode->right=nodeVector[index];
                    treeQueue.push(temNode->left);
                    treeQueue.push(temNode->right);
                }
            }
        }
       
        return nodeVector[0];
    
    }
};