劍指offer----序列化二叉樹

題目描述

請實作兩個函數，分别用來序列化和反序列化二叉樹。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
//題目就是要你設計一套把二叉樹字元化和反字元化的标準，不管你怎麼實作
//運用隊列，層序周遊，在字元化的時候，NULL的輸出‘#’，這樣，所有的結點，
//包括NULL結點也存在于字元化字元串中，同樣，反字元化的時候也是用一個隊列，
//但是這個隊列裡裝的是層序周遊中，上一層不為NULL的n個結點，字元化字元串中
//一定用2n個子字元串與之對應，因為NULL也算一個結點，是以隻要本層結點不為
//NULL結點，則建立一個新結點，并将指向新結點的指針插入隊列，吐過本層結點為
//null結點，則隻需要将上一層對應的指針改為空，不建立新結點，即可。
class Solution {
private:
    string mark_string;
public:
    char* Serialize(TreeNode *root) {
        mark_string="\0";
        queue<TreeNode *> q;
        if(root==NULL)return &mark_string[0];
        
        
        q.push(root);
        while(q.empty()!=true)
        {
            auto mark=q.front();
            q.pop();
            
            if(mark==NULL)
            {
                mark_string+="# ";
                continue;
            }
            
            mark_string+=to_string(mark->val)+' ';
            q.push(mark->left);
            q.push(mark->right);

        }
        return &mark_string[0];
    }
    TreeNode* Deserialize(char* str) {
        if(mark_string.size()==0)return NULL;
        istringstream strm(mark_string);
        string flag_str;
        strm>>flag_str;
        
        TreeNode* root=new TreeNode(atoi(&flag_str[0]));
        queue<TreeNode*> q;
        q.push(root);
        
        while(q.empty()!=true)
        {
            auto mark=q.front();
            q.pop();
            strm>>flag_str;
            if(flag_str=="#")
            {
                mark->left=NULL;
            }
            else
            {
                mark->left=new TreeNode(atoi(&flag_str[0]));
                q.push(mark->left);
            }
            strm>>flag_str;
            if(flag_str=="#")
            {
                mark->right=NULL;
            }
            else
            {
                mark->right=new TreeNode(atoi(&flag_str[0]));
                q.push(mark->right);
            }
        }
        return root;
    }
};