Skip to content

Instantly share code, notes, and snippets.

@crates
Created January 23, 2020 22:46
Show Gist options
  • Save crates/5dc8f2b38d0936a16a75e5802709941a to your computer and use it in GitHub Desktop.
Save crates/5dc8f2b38d0936a16a75e5802709941a to your computer and use it in GitHub Desktop.
Serialize / Deserialize Binary Trees (LeetCode problem)
// Designed to solve this LeetCode problem: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
// Author: Crates McD (https://cr8s.net)
// Runtime: 120 ms, faster than 9.86% of JavaScript online submissions for Serialize and Deserialize Binary Tree.
// Memory Usage: 43 MB, less than 100.00% of JavaScript online submissions for Serialize and Deserialize Binary Tree.
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
const serialize = (root) => {
const queue = [];
const serialized = [];
queue.push(root);
while (queue.length) {
const tmpNode = queue.pop();
if (tmpNode) {
serialized.push(tmpNode.val);
queue.push(tmpNode.right);
queue.push(tmpNode.left);
}
else serialized.push(null);
}
return serialized;
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
const deserialize = (data) => {
if (!data.length || data[0] === null) {
data.shift();
return null;
}
let rootNode = new TreeNode(data.shift());
rootNode.left = deserialize(data);
rootNode.right = deserialize(data);
return rootNode;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment