297. Serialize and Deserialize Binary Tree

Description

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

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * 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 = function (root) {
  let queue = [root];
  let result = '';

  while (queue.length) {
    const nextQueue = [];

    for (const node of queue) {
      if (node) {
        nextQueue.push(node.left, node.right);
        result += `${node.val} `;
        continue;
      }
      result += 'null ';
    }
    queue = nextQueue;
  }
  return result.trimEnd();
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
const deserialize = function (data) {
  const nodes = data.split(' ');
  if (nodes[0] === 'null') return null;
  const root = new TreeNode(nodes[0]);
  const queue = [root];
  const createNode = value => (value === 'null' ? null : new TreeNode(value));

  for (let index = 1; index < nodes.length; index += 2) {
    const node = queue.shift();

    node.left = createNode(nodes[index]);
    node.right = createNode(nodes[index + 1]);
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
  }
  return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */