297. Serialize and Deserialize Binary Tree

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

 

Input: root = [1,2,3,null,null,4,5]

Output: [1,2,3,null,null,4,5]

/**
 * 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 serializeLoop(TreeNode* node){
        // from left to right
        if(!node){
            return "null";
        }
        string ret = to_string(node->val);
        
        return ret + "," + serializeLoop(node->left) + "," + serializeLoop(node->right);
    }
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "[]";
        }
        return "[" + serializeLoop(root) + "]";
    }

    vector<int> tokens;
    
    TreeNode* deserializeLoop(int pos){
        TreeNode* node = new TreeNode(tokens[pos]);
        int leftMove = 2 * pos + 1;
        int rightMove = 2 * pos + 2;
        int tokensLen = tokens.size();
        
        if(leftMove < tokensLen){
            node->left = deserializeLoop(2 * pos + 1);    
        }
        if(rightMove < tokensLen){
            node->right = deserializeLoop(2 * pos + 2);    
        }
        return node;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string token = "";
        for(int i = 1; i < data.size(); i++){
            if(data[i] == ',' || data[i] == ']'){
                if(token == "null"){
                    tokens.push_back(NULL);
                } else {
                    stringstream degree(token);
                    int t = 0;
                    degree >> t;
                    tokens.push_back(t);    
                }
                token = "";
                continue;
            }
            token += data[i];
        }
        
        return deserializeLoop(0);
    }
};

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

 위는 02-09 출근 전에 dfs로 짠 코드이다.  expected sequence를 보고 bfs로 짜야하는 부분을 놓쳤고, string to int에서 leetcode에서는 stoi가 먹히지 않은 부분, bfs로 돌면 맨 마지막 NULL 처리를 어떻게 할 것인지 고민해야한다.

 

/**
 * 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 serializeLoop(TreeNode* node){
        // from left to right
        if(!node){
            return "null";
        }
        string ret = to_string(node->val);
        
        return ret + "," + serializeLoop(node->left) + "," + serializeLoop(node->right);
    }*/
    
    string bfs(TreeNode* node){
        string ret = "[";
        queue<TreeNode*> que;
        
        int normals = 1;
        que.push(node);
        
        while(!que.empty()){
            if(normals == 0){
                break;
            }
            
            TreeNode* cur = que.front();
            que.pop();
            
            if(cur) {
                normals--;
                ret += to_string(cur->val) + ",";
                
                que.push(cur->left);
                if(cur->left){
                    normals++;
                }
                que.push(cur->right);
                if(cur->right){
                    normals++;
                }
            } else {
                ret += "null,";
            }
        }
        ret[ret.size() - 1] = ']';
        return ret;
    }
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "[]";
        }
        return bfs(root);
    }

    vector<int> tokens;
    
    TreeNode* deserializeLoop(){
        TreeNode* node = new TreeNode(tokens[0]);
        queue<TreeNode*> que;
        que.push(node);
        int pos = 1;
        
        while(!que.empty()){
            if(pos >= tokens.size()) break;
            TreeNode* cur = que.front();
            que.pop();
            
            if(cur == NULL) continue;
            
            if(pos < tokens.size() && tokens[pos] != -1001){
                cur->left = new TreeNode(tokens[pos]);    
            }
            if(pos + 1 < tokens.size() && tokens[pos + 1] != -1001)
                cur->right = new TreeNode(tokens[pos + 1]);
            pos += 2;
            
            que.push(cur->left);
            que.push(cur->right);
        }
        return node;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string token = "";
        for(int i = 1; i < data.size(); i++){
            if(data[i] == ',' || data[i] == ']'){
                if(token == "") continue;
                
                if(token == "null"){
                    tokens.push_back(-1001);
                } else {
                    stringstream degree(token);
                    int t = 0;
                    degree >> t;
                    tokens.push_back(t);    
                }
                token = "";
                continue;
            }
            token += data[i];
        } 
        
        if(tokens.empty()) return NULL;
        
        return deserializeLoop();
    }
};

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

 BFS와 NULL 처리 변경인데, solution은 DFS로 되어있어서 스터디할때 한 번 봐야겠다. - 2021-02-10