[LeetCode]Serialize and Deserialize Binary Tree

제목 링크: Serialize and Deserialize Binary Tree
제목:
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as  "[1,2,3,null,null,4,5]"
, just the same as  how LeetCode OJ serializes a binary tree
. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
제목 설명:
제목은 TreeNode 체인 테이블로 저장된 두 갈래 트리에 대해 서열화와 반서열화를 요구하고 마지막으로 원시적인 TreeNode 체인 테이블을 얻으면 성공한다는 것을 설명한다.
제목은 중간 과정에서 얻어지는 서열화 열에 관심이 없기 때문에 리코드가 자주 사용하는 표현법에 구애받지 않고 자신의 표현법을 사용할 수 있다.
재건을 편리하게 하기 위해서, 우리는 앞의 순서를 두루 훑어보고, NULL 아이를 만날 때마다 # 문자를 저장합니다.
이렇게 하면 제목이 제시한 나무를 저장할 때 우리는 [1,2,#,#,#,3,4,#,#,5,#,#,]라는 문자열을 얻을 수 있다.
복원할 때 이 서열화된 열을 앞의 서열에 따라 해석하기만 하면 됩니다. 사용하는 핵심 방법은 문자열의substr,find 방법입니다. 이 방법에서 자주 사용하는 형식은 두 가지가 있습니다. ①str.substr(location)입니다. 이 방법은str가location에서 끝까지 이어지는 문자열을 되돌려줍니다.②str.substr(location,len). 이 방법은 [location,location+len) 구간의 문자열을 되돌려줍니다. 오른쪽은 열린 구간입니다. str.find(charset)는str에서 처음으로 일치하는 charset의 위치를 되돌려줍니다.
[구체적 실현]
귀속을 편리하게 하기 위해서 우리는 두 가지 유형의 사유 방법을 정의한다.
1. 서열화
앞의 규칙에 따라 루트에 접근합니다. 루트가 NULL인 경우 #, 다른 경우 결합점의 숫자를 연결하고 문자열로 변환하기 위해stringstream을 사용합니다.
2. 반서열화
귀속 함수의 매개 변수는 (TreeNode*&root,string&data)입니다. 데이터가 분할된 값 val에 따라 root의 값을 결정합니다. 만약 val이 #이라면 이것은 빈 결점입니다. root=NULLL을 직접 명령합니다. 그렇지 않으면 새로운 TreeNode를 root로 만듭니다.str () 방법은char* 문자열을 얻어 루트의 좌우 아들에게 계속 귀속합니다. 이때 전송된 데이터는 처리된 부분을 제거한 문자열입니다.반서열화된 귀속 순서는 전 서열의 반복과 일치한다.
코드는 다음과 같습니다.

/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        preOrderSerialize(root,res);
        cout << res;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        TreeNode *root = NULL;
        preOrderDeserialize(root,data);
        return root;
    }
private:

    void preOrderSerialize(TreeNode *root, string &str){
        if(!root){
            str += "#,";
            return;
        }
        stringstream ss;
        ss << root->val;
        str += ss.str();
        str += ",";
        preOrderSerialize(root->left,str);
        preOrderSerialize(root->right,str);
    }
    
    void preOrderDeserialize(TreeNode *&root, string &data){
        if(data.length() == 0) return;
        string tmp = data.substr(0,data.find(','));
        data = data.substr(data.find(',')+1);
        if(tmp.compare("#") == 0) root = NULL;
        else{
            root = new TreeNode(atoi(tmp.c_str()));
            preOrderDeserialize(root->left,data);
            preOrderDeserialize(root->right,data);
        }
    }
    
};



// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));