Serialize and Deserialize Binary Tree Solutions in C++

// Source : https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
// Author : Hao Chen
// Date   : 2015-11-10



#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;

/**
 * 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) {
        return serialize02(root);
        return serialize01(root);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return deserialize02(data);
        return deserialize01(data);
    }      
    

/*
 * ===============================================================================
 *  Using pre-order to serialize and deserialize the tree. 
 * ===============================================================================
 */
public:
    // Encodes a tree to a single string.
    string serialize01(TreeNode* root) {
         string result;
         vector<TreeNode*> v;
         serializeHelper(root, v);
         for(int i=0; i<v.size(); i++){
             result = result + (v[i]==NULL ? "#" : to_string(v[i]->val)) + " ";
         }
         return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize01(string data) {
        vector<TreeNode*> v;
        split(data, ' ', v);

        int index = 0;
        return deserializeHelper(v, index);

    }    

private:

    void serializeHelper(TreeNode* root, vector<TreeNode*>& v) {
        if (root==NULL) {
            v.push_back(NULL);
        }else{
            v.push_back(root);
            serializeHelper(root->left, v);
            serializeHelper(root->right, v);
        }
    }
   

    TreeNode* deserializeHelper(vector<TreeNode*> &v, int& index) {

        if (index >= v.size() ) return NULL;

        TreeNode* root = v[index++];
        if (root) {
            root->left = deserializeHelper(v, index);
            root->right = deserializeHelper(v, index);
        }
        return root;
    }


   void split(const string &s, char delim, vector<TreeNode*> &elems) {
        stringstream ss(s);
        string item;
        while (getline(ss, item, delim)) {
            TreeNode* node =  (item=="#" ? NULL : new TreeNode( stoi(item)) );
            elems.push_back(node);
        }

    }
    

/*
 * ===============================================================================
 *  Using sstream instead of vector to improve the performance
 * ===============================================================================
 */

public:
    // Encodes a tree to a single string.
    string serialize02(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize02(string data) {
        istringstream in(data);
        return deserialize(in);
    } 
    
private:
   void serialize(TreeNode* root, ostringstream& out) {
        if (root==NULL) {
            out << "# ";
            return;
        }
        out << root->val << " ";
        serialize(root->left, out);
        serialize(root->right, out);
    }

    TreeNode* deserialize(istringstream& in) {
        string val;
        in >> val;
        if (val == "#" || val.empty() ) return NULL;

        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserialize(in);
        node->right = deserialize(in);
        return node;
    }
};

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


int main(int argc, char** argv) 
{
    string s = "1 2 3 # # 4 5";
    if (argc>1){
        s = argv[1];
    }
    cout << s << endl;
    Codec codec;
    cout << codec.serialize(codec.deserialize(s)) << endl;
    
    return 0;
    
}

/// Source : https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-09-17

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;


/// BFS
/// Time Complexity: O(n)
/// Space Complexity: 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) {

        if(!root)
            return "[null]";

        string ret = "[";

        queue<TreeNode*> q;
        q.push(root);
        ret += to_string(root->val);
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();

            if(cur->left){
                ret += "," + to_string(cur->left->val);
                q.push(cur->left);
            }
            else
                ret += ",null";

            if(cur->right){
                ret += "," + to_string(cur->right->val);
                q.push(cur->right);
            }
            else
                ret += ",null";
        }
        return ret + "]";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> vec = get_vector(data);

        if(vec.size() == 0 || (vec.size() == 1 && vec[0] == "null"))
            return NULL;

        TreeNode* root = new TreeNode(atoi(vec[0].c_str()));
        queue<TreeNode*> q;
        q.push(root);
        int index = 1;
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();

            assert(vec.size() - index >= 2);
            if(vec[index] != "null"){
                cur->left = new TreeNode(atoi(vec[index].c_str()));
                q.push(cur->left);
            }
            index ++;

            if(vec[index] != "null"){
                cur->right = new TreeNode(atoi(vec[index].c_str()));
                q.push(cur->right);
            }
            index ++;
        }
        return root;
    }

private:
    vector<string> get_vector(const string& data){

        string s = data.substr(1, data.size() - 2) + ",";

        vector<string> res;
        int i = 0;
        while(i < s.size()){
            int comma = s.find(',', i);
            res.push_back(s.substr(i, comma - i));
            i = comma + 1;
        }
        return res;
    }
};


int main() {

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    string s = Codec().serialize(root);
    cout << s << endl;

    TreeNode* x = Codec().deserialize(s);
    cout << Codec().serialize(x) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-09-17

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// DFS
/// Time Complexity: O(n)
/// Space Complexity: 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) {

        if(!root)
            return "[null]";

        string ret = "[";
        dfs(root, ret);
        ret.pop_back();
        return ret + "]";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> vec = get_vector(data);

        if(vec.size() == 0 || (vec.size() == 1 && vec[0] == "null"))
            return NULL;

//        for(const string& s: vec)
//            cout << s << " ";
//        cout << endl;

        int index = 0;
        return dfs(vec, index);
    }

private:
    TreeNode* dfs(const vector<string>& vec, int& index){

        if(index == vec.size() || vec[index] == "null")
            return NULL;

        TreeNode* node = new TreeNode(atoi(vec[index].c_str()));
        index ++;
        node->left = dfs(vec, index);

        index ++;
        node->right = dfs(vec, index);

        return node;
    }

    void dfs(TreeNode* node, string& ret){

        ret += to_string(node->val) + ",";

        if(node->left)
            dfs(node->left, ret);
        else
            ret += "null,";

        if(node->right)
            dfs(node->right, ret);
        else
            ret += "null,";
    }

    vector<string> get_vector(const string& data){

        string s = data.substr(1, data.size() - 2) + ",";

        vector<string> res;
        int i = 0;
        while(i < s.size()){
            int comma = s.find(',', i);
            res.push_back(s.substr(i, comma - i));
            i = comma + 1;
        }
        return res;
    }
};


int main() {

    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    string s = Codec().serialize(root);
    cout << s << endl;

    TreeNode* x = Codec().deserialize(s);
    cout << Codec().serialize(x) << endl;

    return 0;
}