Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

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

Serialize and Deserialize Binary Tree - LeetCode

Language: C++

space 와 time 은 O(N)

/**
 * 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 value;
        
        serializeHelper(root, value);
        // serializeBFS(root, value);
        
        return value;
    }
    
    void serializeBFS(TreeNode* root, string& value) {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node)
                value += to_string(node->val) + ",";
            else
                value += "nullptr,";
            
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
    
    void serializeHelper(TreeNode* root, string& value) {
        if (root) {
            value += to_string(root->val) + ",";
            serializeHelper(root->left, value);
            serializeHelper(root->right, value);
        } else {
            value += "null,";
        }
       
    }
    
    TreeNode *dfs(int &index, vector<string> &nodes)
    {
        TreeNode *node = NULL;
        string &nodeVal = nodes[index];
        index ++;
        if (nodeVal != "null")
        {
            node = new TreeNode(stoi(nodeVal, nullptr, 10));
            node->left = dfs(index, nodes);
            node->right = dfs(index, nodes);
        }
        
        return node;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        // cout << data << endl;
        size_t pos = -1;
        string delimiter = ",";
        string token;
        vector<string> nodes;
        while ((pos = data.find(delimiter)) != std::string::npos) {
            token = data.substr(0, pos);
            data.erase(0, pos + delimiter.length());
            nodes.push_back(token);
        }
        
        int index = 0;
        
        return dfs(index, nodes);
    }
    
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

 

시도

/**
 * 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 value;
        
        // serializeHelper(root, value);
        serializeBFS(root, value);
        
        return value;
    }
    
    void serializeBFS(TreeNode* root, string& value) {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node)
                value += to_string(node->val) + ",";
            else
                value += "nullptr,";
            
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
    
    void serializeHelper(TreeNode* root, string& value) {
        if (root) {
            value += to_string(root->val) + ",";
            serializeHelper(root->left, value);
            serializeHelper(root->right, value);
        } else {
            value += "null,";
        }
       
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        
        queue<string> q;
        TreeNode* root;
        
        if (data.length() > 0) {
            // , 찾아서 q 에 넣고
            // 하나 빼고 그 둘 자식 두 개 뽑고
            // 큐에도 자식 두 개 넣고
            string value = data.substr(0, data.find(","));
            q.push(value);
            
            root = new TreeNode();
            
            while (!q.empty()) {
                
                string temp = q.front();
                q.pop();
                
                
                if (temp != "null")
                    root->val = stoi(temp);
                else 
                    continue;
                
                // left
                string left = data.substr(0, data.find(","));
                if (left != "null") {
                    TreeNode* leftNode = new TreeNode();
                    leftNode->val = stoi(left);
                    root->left = leftNode;
                }
                q.push(left);
                // right
                string right = data.substr(0, data.find(","));
                if (right != "null") {
                    TreeNode* rightNode = new TreeNode();
                    rightNode->val = stoi(right);
                    root->right = rightNode;
                }
                q.push(right);
            }
            
        }
            
        
        
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

/**
 * 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 value;
        
        serializeHelper(root, value);
        // serializeBFS(root, value);
        
        return value;
    }
    
    void serializeBFS(TreeNode* root, string& value) {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node)
                value += to_string(node->val) + ",";
            else
                value += "nullptr,";
            
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
    
    void serializeHelper(TreeNode* root, string& value) {
        if (root) {
            value += to_string(root->val) + ",";
            serializeHelper(root->left, value);
            serializeHelper(root->right, value);
        } else {
            value += "null,";
        }
       
    }
    
    TreeNode* deserializeHelper(string& data) {
        
        string value = data.substr(0, data.find(","));
        
        data = data.substr(data.find(",") + 1, data.length() - 1);
        
        if (value == "null" || value.length() == 0) {
            return nullptr;
        }
        
        
        TreeNode* root = new TreeNode(stoi(value));
        
        root->left = deserializeHelper(data);
        root->right = deserializeHelper(data);
        
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize1(string data) {
        
        TreeNode* root = deserializeHelper(data);
        
        /*
        queue<string> q;
        
        if (data.length() > 0) {
            // , 찾아서 q 에 넣고
            // 하나 빼고 그 둘 자식 두 개 뽑고
            // 큐에도 자식 두 개 넣고
            string value = data.substr(0, data.find(","));
            q.push(value);
            
            root = new TreeNode();
            
            while (!q.empty()) {
                
                string temp = q.front();
                q.pop();
                
                
                if (temp != "null")
                    root->val = stoi(temp);
                else 
                    continue;
                
                // left
                string left = data.substr(0, data.find(","));
                if (left != "null") {
                    TreeNode* leftNode = new TreeNode();
                    leftNode->val = stoi(left);
                    root->left = leftNode;
                }
                q.push(left);
                // right
                string right = data.substr(0, data.find(","));
                if (right != "null") {
                    TreeNode* rightNode = new TreeNode();
                    rightNode->val = stoi(right);
                    root->right = rightNode;
                }
                q.push(right);
            }
            
        }
        */    
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

문제점

문제에 있는 테스트 케이스처럼 BFS 로 풀려다가 안되서 discuss 참고해서 DFS로도 되는지 알게 되서 짜보다가

serialize는 잘 한 것 같은데 deserialize 가 문제였다. 짜긴 짜도 계속 시간 오래걸린다고 나와서 

다른 discussion 보니까 stringstream 을 사용하더라. 그리고 위에 맨처음 첨부한 소스처럼 다른 함수들 사용하고, list를 한번에 만들어서 전달해서 사용하더라;....

 

이 문제를 마지막으로 binary tree 관련된 코스가 끝이 났다...

마지막 문제는 쉽게 풀 수 있을 줄 알았는데...

주말에 카페는 너무 시끄럽고 사람도 많고 나도 쉬고싶어서 머리가 너무 아프다;; 잉...

다들 웃음이 많다 나만 재미없나보다 ㅠ