lintcode 이 진 트 리 의 직렬 화 와 반 직렬 화

알고리즘 을 설계 하고 코드 를 작성 하여 이 진 트 리 를 직렬 화하 고 역 직렬 화 합 니 다.트 리 를 파일 에 기록 하 는 것 을 '직렬 화' 라 고 하 며, 파일 을 읽 고 같은 이 진 트 리 를 재 구축 하 는 것 을 '반 직렬 화' 라 고 합 니 다.이 진 트 리 를 어떻게 역 직렬 화 하거나 직렬 화 하 는 지 는 제한 이 없습니다. 이 진 트 리 를 하나의 문자열 로 직렬 화 할 수 있 고 문자열 을 원래 의 트 리 구조 로 반 직렬 화 할 수 있 도록 확보 해 야 합 니 다.
샘플 은 테스트 데이터 샘플 을 보 여 줍 니 다. 이 진 트 리 {3, 9, 20, \ #, \ #, 15, 7} 은 다음 과 같은 트 리 구 조 를 표시 합 니 다.

  3
 / \
9  20
  /  \
 15   7

이 문 제 는 재 귀 와 비 재 귀 두 가지 해법 이 있 는데, 먼저 재 귀 해법 을 본다.우선 입 출력 문자 직렬 istringstream 과 ostringstream 에 접속 해 야 합 니 다.직렬 화 에 대해 서 는 루트 노드 부터 존재 하면 출력 흐름 에 값 을 저장 한 다음 에 좌우 부분 노드 를 재 귀적 으로 합 니 다.역 직렬 화 에 대해 먼저 한 문 자 를 읽 고 뿌리 노드 를 생 성 한 다음 에 뿌리 노드 의 좌우 부분 노드 를 재 귀적 으로 한다. 코드 는 다음 과 같다.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        ostringstream out;
        serialize(root, out);
        return out.str();
    }
    
    void serialize(TreeNode *root, ostringstream &out) {
        if (root) {
            out << root->val << ' ';
            serialize(root->left, out);
            serialize(root->right, out);
        } else {
            out << "# ";
        }
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
        istringstream in(data);
        return deserialize(in);
    }
    
    TreeNode* deserialize(istringstream &in) {
        string val;
        in >> val;
        if (val == "#") return nullptr;
        TreeNode *root = new TreeNode(stoi(val));
        root->left = deserialize(in);
        root->right = deserialize(in);
        return root;
    }
};

다른 하 나 는 비 재 귀 해법 으로 약간 복잡 하 므 로 quue 를 통 해 해 해 야 한다. 본질은 BFS 알고리즘 이다.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        ostringstream out;
        queue q;
        if (root) q.push(root);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (t) {
                out << t->val << ' ';
                q.push(t->left);
                q.push(t->right);
            } else {
                out << "# ";
            }
        }
        return out.str();
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
        if (data.empty()) return nullptr;
        istringstream in(data);
        queue q;
        string val;
        in >> val;
        TreeNode *res = new TreeNode(stoi(val)), *cur = res;
        q.push(cur);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (!(in >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->left = cur;
            }
            if (!(in >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->right = cur;
            }
        }
        return res;
    }
};