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.
- order of output is breath first
- push nodes into queue and serialize values
- remove any null values from the end of array
- stringify array
- parse input as into array
- takes first three vals, as root, left, right
- if values of left and right child exist
- push them back into queue for their child nodes to be added if available
Solution
var serialize = function (root) {
let output = [];
let queue = root ? [root] : [];
while (queue.length) {
let node = queue.shift();
if (node) {
output.push(node.val);
queue.push(node.left || null);
queue.push(node.right || null);
} else {
output.push(null);
}
}
while (output[output.length - 1] === null) {
output.pop();
}
return JSON.stringify(output);
};
var deserialize = function (data) {
const arr = JSON.parse(data);
if (!arr.length) return null;
const root = new TreeNode(arr.shift());
const queue = [root];
while (queue.length) {
let node = queue.shift(),
val;
node.left = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;
node.right = (val = arr.shift()) || val === 0 ? new TreeNode(val) : null;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return root;
};
