LeetCode 297. Serialize and Deserialize Binary Tree

문제

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

걸린 시간

- 실패

틀린 풀이

C++

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

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        // 노드가 존재하지 않을 때
        if(root == nullptr) return s;
        // 노드가 하나만 존재할 때
        if(root->left == nullptr && root->right == nullptr){
            s += to_string(root->val);
            return s;
        }
        // 두개 이상의 노드가 존재할 때
        queue<TreeNode*> q;
        q.push(root);
        vector<int> tree;
        while(tree.size() <= 1e4){
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr){
                tree.push_back(NULL_PTR);
                q.push(nullptr);
                q.push(nullptr);
                continue;
            }
            else{
                tree.push_back(node->val);
            }
            q.push(node->left);
            q.push(node->right);
        }
        s += to_string(tree[0]);
        for(int i = 1; i < tree.size(); i++){
            if(tree[i] == NULL_PTR) s += ",null";
            else s += "," + to_string(tree[i]);
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        cout << data;
        istringstream iss(data);
        string token;
        vector<int> tree;
        tree.push_back(NULL_PTR);
        while(getline(iss, token, ',')){
            if(token == "null") tree.push_back(NULL_PTR);
            else tree.push_back(stoi(token));
        }
        if(tree.empty()) return nullptr;
        // makeTree
        vector<TreeNode*> ret(tree.size()+1, nullptr);
        for(int i = 1; i < tree.size(); i++)
            if(tree[i] != NULL_PTR) ret[i] = new TreeNode(tree[i]);
        for(int i = 1; i < tree.size(); i++){
            if(ret[i] == nullptr) continue;
            if(i*2 < tree.size()) ret[i]->left = ret[i*2];
            if(i*2+1 < tree.size()) ret[i]->right = ret[i*2+1];
        }
        return ret[1];
    }
};

완전 이진트리로 생각하여 노드가 존재하지 않는 빈 공간까지 모두 1차원 배열에 저장한 후 인덱싱을 이용해 원래 트리 형태로 복구하는 풀이 방법이다.

노드의 개수가 아닌 null 을 포함한 원소가 최대 1e4 개 있다고 잘못 해석하여 시도했던 방법으로, 트리가 편향되었을 경우 깊이가 최대 1e4 까지 커질 수 있어 null 이 차지하는 공간이 지수적으로 증가하므로 틀린 풀이다.

옳은 풀이

C++

/**
 * 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 s;
        // 노드가 존재하지 않을 때
        if(root == nullptr) return s;
        // 노드가 하나만 존재할 때
        if(root->left == nullptr && root->right == nullptr){
            s += to_string(root->val);
            return s;
        }
        // 두개 이상의 노드가 존재할 때
        queue<TreeNode*> q;
        q.push(root);
        vector<string> nums;
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr){
                nums.push_back("null");
                continue;
            }
            else{
                nums.push_back(to_string(node->val));
            }
            q.push(node->left);
            q.push(node->right);
        }
        s += nums[0];
        for(int i = 1; i < nums.size(); i++)
            s += "," + nums[i];
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream iss(data);
        string token;
        vector<string> nums;
        while(getline(iss, token, ','))
            nums.push_back(token);
        // 노드가 존재하지 않을 때
        if(nums.empty()) return nullptr;
        TreeNode* root = new TreeNode(atoi(nums[0].c_str()));
        // 노드가 하나만 존재할 때
        if(nums.size() == 1) return root;
        // 두개 이상의 노드가 존재할 때
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node == nullptr) continue;
            if(nums[i] == "null") node->left = nullptr;
            else node->left = new TreeNode(atoi(nums[i].c_str()));
            if(nums[i+1] == "null") node->right = nullptr;
            else node->right = new TreeNode(atoi(nums[i+1].c_str()));
            q.push(node->left);
            q.push(node->right);
            i += 2;
        }
        return root;
    }
};

주어진 트리를 문자열로 변경할 때와 동일하게, 큐를 이용하여 트리를 생성할 수 있었다.