序列化、反序列化二叉樹

序列化：用前序周遊，生成字元串。

反序列化：将字元串根據分隔符（逗号），切割成子字元串

需要注意的是，周遊時我們一般用void 傳回值，将周遊值儲存在數組中

，生成樹時，一般用樹節點作為傳回值

//周遊的模闆
void proess(TreeNode* root,vector<int>& my_vec)
    {
        if(root == nullptr)return ;
        proess(root->left,my_vec);
        my_vec.emplace_back(root->val);
        proess(root->right,my_vec);
    }  


//生成樹模闆
 TreeNode* preoss(vector<int>& nums,int left,int right){   //遞歸建立一個二叉樹
        if(right<left){     //base case;
            return nullptr;   //傳回空
        }
        int mid = (right+left)/2;
        TreeNode* head = new TreeNode(nums[mid]);
        head->left = preoss(nums,left,mid-1);  //根據遞歸規則，如果base case 不滿足，這個節點就有值
        head->right = preoss(nums,mid+1,right);
        return head;
    }
           

解答過程：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    //序列化  //周遊的過程 使用前序周遊
    string serialize(TreeNode* root) {
        string  my_str = "";
        proess(root,my_str);
        //my_str.pop_back();
        //std::cout<<my_str<<std::endl;
        return my_str;
    }
    //反序列化  //建樹的過程
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //queue<string> my_str;
        vector<string> my_str;
        vector<int> index;
        for(int i = 0;i<data.size();i++)
        {
            if(data[i] == ',')index.emplace_back(i);
        }
        int first = 0;
        for(int j = 0;j<index.size();j++){
            string mid(data.begin()+first,data.begin()+index[j]);
            my_str.push_back(mid);

            //std::cout<<mid<<std::endl;
            first = index[j]+1;
        }
        /*
        for(auto i : my_str)
        {
            std::cout<<i<<std::endl;
        }*/
        int ind = 0;
        return pro(my_str,ind);
    }
    TreeNode* pro(vector<string>& my_str,int& index)   //建立一顆二叉樹，傳回樹節點
    {
        if(my_str[index] == "null" || index>=(my_str.size()-1))
        {
            return nullptr;
        }
        TreeNode* head = new TreeNode(atoi(my_str[index].c_str()));
        index++;
        head->left = pro(my_str,index);
        index++;
        head->right = pro(my_str,index);
        return head;
    }
    void proess(TreeNode* root, string& my_str)
    {
        if(root == nullptr)
        {
            my_str +="null,";
            return ;
        }
        my_str += std::to_string(root->val); //轉換成字元串的格式
        my_str.push_back(',');
        proess(root->left,my_str);
        proess(root->right,my_str);
    }
};
//2021.4.16
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));