297. 二叉树的序列化与反序列化

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

来源：LeetCode

示例：

略。

思路

采用广度优先搜索，按层次遍历节点，用字符串记录结果，即序列化。然后跟你字符串解析构建出一棵树，即反序列化。

这里采用一个字符作为分割符，将层次遍历结果依次排列开，注意如果有空值，则连续两个分割符，中间空字符串来表示此处有一个空节点。

解法

const splitChar = '*';

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
const serialize = root => {
  const queue = [];
  let result = '';

  if (root) queue.push(root);

  while (queue.length) {
    const node = queue.shift();

    if (node) {
      result += node.val;
      queue.push(node.left);
      queue.push(node.right);
    }

    result += splitChar;
  }

  return result;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
const deserialize = data => {
  const makeNode = char => {
    if (!char) return null;

    return new TreeNode(Number(char));
  };

  if (data === '') return null;

  const array = data.split(splitChar);

  const root = makeNode(array.shift());
  const queue = [root];
  let index = 0;

  while (queue.length) {
    const node = queue.shift();

    node.left = makeNode(array[index++]);
    node.right = makeNode(array[index++]);

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }

  return root;
};