Leetcode Serialize and Deserialize Binary Tree problem solution YASH PAL, 31 July 2024 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. 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