Leetcode Serialize and Deserialize Binary Tree problem solution

YASH PAL,

In this Leetcode Serialize and Deserialize Binary Tree problem solution Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Leetcode Serialize and Deserialize Binary Tree problem solution

Problem solution in Python.

from collections import deque

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        get_val = lambda item: item.val if item else None
        q = deque()
        
        if not root:
            return str([])
        else:
            res = [root.val]
            q.append(root)
        while q:
            l=[]
            len_q = len(q)
            for i in range(len_q):
                item = q.popleft()
                if item and item.left:
                    q.append(item.left)
                if item and item.right:
                    q.append(item.right)
                l.append(get_val(item.left))
                l.append(get_val(item.right))
            if not all(x is None for x in l):
                res += l
        ind =len(res)
        for i in res[::-1]:
            if i is not None:break
            else:ind-=1
        return str(res[:ind])
                     
   def deserialize(self, data):
        if len(data)==0 or data=='[]':
            return []
        de_data = data[1:-1].split(', ')
        return [int(d) if d!='None' else None for d in de_data]

Problem solution in Java.

public class Codec {
    List<String> count;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        count = new ArrayList<>();
        iter(root, 1);
        count.remove(0);
        String ret = "";
        for (String i: count){
            ret = ret+i;
            ret = ret+",";
        }
        ret.substring(0, ret.length()-1);
        return ret;
    }
    
    public void iter(TreeNode root, int index){
        if (root == null) return;
        while (index >= count.size())
            count.add(new String("n"));
        count.add(index, String.valueOf(root.val));
        iter(root.left, index*2);
        iter(root.right, index*2+1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] raw = data.split(",");
        return iter2(raw, 1);
    }
    
    public TreeNode iter2(String[] raw, int index){
        if (raw[index-1] == "n")
            return null;
        TreeNode cur = new TreeNode(Integer.valueOf(raw[index-1]));
        cur.left = iter2(raw, index*2);
        cur.right = iter2(raw, index*2+1);
        return cur;
    }
}

Problem solution in C++.

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL)   return " ";
        list<TreeNode*> ver;
        ver.push_back(root);
        string str;
        while(!ver.empty()) {
            TreeNode* tr = ver.front();
            ver.pop_front();
            if (tr == NULL) {
                str.append(":,");
                continue;
            } else {
                string s = to_string(tr->val) + ",";
                str.append(s);
            }
            ver.push_back(tr->left);
            ver.push_back(tr->right);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == " ")    return NULL;
        int id = data.find(',');
        string s;
        
        s = data.substr(0, id);
        id += 1;
        int val = stoi(s);
        TreeNode* root = new TreeNode(val);
        list<TreeNode*> ver;
        ver.push_back(root);
        while(!ver.empty()) {
            TreeNode* tr = ver.front();
            ver.pop_front();
            vector<string> v;
            for (int i = 0; i < 2; i++) {
                int idx = data.find(',', id);
                s = data.substr(id, idx - id);
                id = idx + 1;
                v.push_back(s);
                s.clear();
            }
            if (v[0] != ":")    tr->left = new TreeNode(stoi(v[0]));
            if (v[1] != ":")    tr->right = new TreeNode(stoi(v[1]));
            if (tr->left)   ver.push_back(tr->left);
            if (tr->right)  ver.push_back(tr->right);
        }
        return root;
    }
};

Problem solution in C.

#define WIDE_RANGE

#ifdef WIDE_RANGE
#define KEY_MASK    0x1ffff
typedef uint32_t keyy_t;
#else
#define KEY_MASK    0xffff
typedef uint16_t keyy_t;
#endif // WIDE_RANGE

#define KEY(a)      ((uintptr_t)(a) & KEY_MASK)

struct srlz_data {
    int val;
    keyy_t loff, roff;   
} __attribute__ ((packed));

struct srlz {
    size_t sz; // To help on-disk storage/retrieval, etc
    size_t n;
    struct srlz_data z[100000];
} __attribute__ ((packed));
    
char* serialize(struct TreeNode* root) {
    int of[KEY_MASK] = { 0 }, i = 1, k;
    struct TreeNode *n[10000] = { root };
    struct srlz *d = malloc(sizeof *d);
    struct srlz_data *z = d->z;
    d->sz = sizeof *d;
    of[KEY(root)] = i++;        
    for (int f = 0, b = 1 ; root && f < b ; f++) {
        z[of[k = KEY(n[f])]].val = n[f]->val;
        z[of[k]].loff = n[f]->left ? of[KEY(n[b++] = n[f]->left)] = i++ : 0;
        z[of[k]].roff = n[f]->right ? of[KEY(n[b++] = n[f]->right)] = i++ : 0;
    }
    return d->n = root ? i : 0, (char *)d;
}

struct TreeNode* deserialize(char* data) {
    struct srlz *d = (void *)data;
    struct srlz_data *z = d->z + 1;
    size_t c = d->n;
    struct TreeNode *n[100000] = { [1] = c ? malloc(sizeof **n) : NULL };
    for (int i = 1 ; i < c ; n[i++]->val = z++->val) {
        n[i]->left = z->loff ? n[z->loff] = malloc(sizeof **n) : NULL;
        n[i]->right = z->roff ? n[z->roff] = malloc(sizeof **n) : NULL;
    }
    return n[1];
}

coding problems