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

Leetcode Serialize and Deserialize Binary Tree 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]

Serialize and Deserialize Binary Tree 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 solutions Leetcode Problems Solutions

Leave a Reply

Your email address will not be published. Required fields are marked *