Algorithm
Problem Name: 297. Serialize and Deserialize Binary Tree
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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -1000 <= Node.val <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int depth(struct TreeNode *n) {
int l, r;
if (!n) return 0;
l = depth(n->left);
r = depth(n->right);
return l > r ? l + 1 : r + 1;
}
#define PUSH(P, N) do { P[sp++] = N; } while (0)
#define POP(P, N) do { N = P[--sp]; } while (0)
/** Encodes a tree to a single string. */
char* serialize(struct TreeNode* root) {
char *str, *head;
int sz = 1024 * 10;
int d, n = 0, l = 0;
struct TreeNode **stack;
int sp = 0;
struct TreeNode *node;
char c;
#define HEAD_SZ 32
if (!root) return NULL;
d = depth(root);
head = malloc(sz * (sizeof(int) + 2) + HEAD_SZ + 1);
stack = malloc((d + 1) * sizeof(struct TreeNode *));
//assert(head && stack);
str = head + HEAD_SZ;
PUSH(stack, root);
while (sp) {
if (l + 32 + 8 > sz) {
sz = sz * 2;
head = realloc(head, sz * (sizeof(int) + 2) + HEAD_SZ + 1);
//assert(head);
str = head + l + HEAD_SZ;
}
POP(stack, node);
if (node) {
n ++;
sprintf(str, "%08x", node->val);
str += 8; l += 8;
PUSH(stack, node->right);
PUSH(stack, node->left);
} else {
*str = ','; str += 1; l += 1;
}
}
*str = 0;
// put checksum in the first 8 bytes
c = head[HEAD_SZ];
sprintf(head, "%08x%08x%08x%08x", 0, d, n, l);
head[HEAD_SZ] = c; //sprintf has put a 0 terminator in the end.
free(stack);
return head;
}
int str2num(char *p) {
char buff[9] = { 0 };
strncpy(buff, p, 8);
return strtol(buff, NULL, 16);
}
/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
int n, d, l;
struct TreeNode *buff;
int idx = 0;
struct TreeNode ***stackp;
int sp = 0;
struct TreeNode **pp;
int val;
struct TreeNode *root = NULL, *node;
if (!data) return NULL; // verify checksum
data += 8;
d = str2num(data);
data += 8;
n = str2num(data);
data += 8;
l = str2num(data);
data += 8;
buff = malloc(n * sizeof(struct TreeNode));
stackp = malloc((d + 1) * sizeof(struct TreeNode **));
//assert(buff && stackp);
PUSH(stackp, &root);
while (l > 0) {
POP(stackp, pp);
if (*data == ',') {
*pp = NULL;
data += 1;
l -= 1;
} else {
val = str2num(data);
data += 8;
l -= 8;
node = &buff[idx ++];
node->val = val;
*pp = node;
PUSH(stackp, &node->right);
PUSH(stackp, &node->left);
}
}
free(stackp);
return root;
}
Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Codec {
private:
unordered_maptree2string;
unordered_map < string, TreeNode*>string2tree;
int count = 0;
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string s = to_string(count++);
tree2string[root] = s;
string2tree[s] = root;
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return string2tree[data];
}
};
Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]
#3 Code Example with Java Programming
Code -
Java Programming
public class Codec {
private static final String NULL_VALUE = "-";
private static final String DELIMETER = " ";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return NULL_VALUE;
}
StringBuilder sb = new StringBuilder();
Stack < TreeNode> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode removed = stack.pop();
if (removed == null) {
sb.append(NULL_VALUE).append(DELIMETER);
continue;
}
sb.append(removed.val).append(DELIMETER);
stack.push(removed.right);
stack.push(removed.left);
}
return sb.toString().trim();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue < String> queue = new LinkedList<>(Arrays.asList(data.split("\\s+")));
return helper(queue);
}
private TreeNode helper(Queue < String> queue) {
if (queue.peek().equals(NULL_VALUE)) {
queue.remove();
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(queue.peek()));
queue.remove();
root.left = helper(queue);
root.right = helper(queue);
return root;
}
}
Input
root = []
Output
[]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const serialize = function(root) {
return rserialize(root, "");
};
function rserialize(root, str) {
if (root === null) {
str += "null,";
} else {
str += root.val + ",";
str = rserialize(root.left, str);
str = rserialize(root.right, str);
}
return str;
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
const deserialize = function(data) {
let data_array = data.split(",").filter(el => el !== "");
return rdeserialize(data_array);
};
function rdeserialize(l) {
if (l[0] === "null") {
l.shift();
return null;
}
const root = new TreeNode(+l[0]);
l.shift();
root.left = rdeserialize(l);
root.right = rdeserialize(l);
return root;
}
Input
root = []
Output
[]
#5 Code Example with Python Programming
Code -
Python Programming
class Codec:
def serialize(self, root):
q, s = root and collections.deque([root]), ""
while q:
node = q.popleft()
if node is None:
s += "null#"
else:
s += str(node.val) + "#"
q += [node.left, node.right]
return s
def deserialize(self, data):
data = data and collections.deque(data.split("#"))
q, root = data and collections.deque([TreeNode(int(data.popleft()))]), None
while q:
node = q.popleft()
if not root:
root = node
l, r = data.popleft(), data.popleft()
if l != "null":
node.left = TreeNode(int(l))
q.append(node.left)
if r != "null":
node.right = TreeNode(int(r))
q.append(node.right)
return root
Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0297_SerializeandDeserializeBinaryTree
{
private readonly char SPLITTER = ',';
private readonly string NULL_VALUE = "null";
// Encodes a tree to a single string.
public string Serialize(TreeNode root)
{
var sb = new StringBuilder();
Serialize(root, sb);
return sb.ToString();
}
private void Serialize(TreeNode root, StringBuilder sb)
{
if (root == null) sb.Append(NULL_VALUE).Append(SPLITTER);
else
{
sb.Append(root.val.ToString()).Append(SPLITTER);
Serialize(root.left, sb);
Serialize(root.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode Deserialize(string data)
{
var splits = data.Split(SPLITTER);
var list = new LinkedList < string>(splits);
return Deserialize(list);
}
private TreeNode Deserialize(LinkedList < string> data)
{
if (data.First.Value == NULL_VALUE)
{
data.Remove(data.First);
return null;
}
var root = new TreeNode(int.Parse(data.First.Value));
data.Remove(data.First);
root.left = Deserialize(data);
root.right = Deserialize(data);
return root;
}
}
}
Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]