[297] 二叉树的序列化与反序列化

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

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 /

反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例：

你可以将以下二叉树：

⁠ ⁠  ⁠1

⁠ ⁠ /⁠ \

 2  3

    / \

    4 5

序列化为 "[1,2,3,null,null,4,5]"

提示：这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode

序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明：不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

这道题能帮助我们了解 leetcode 到底是怎样使用基本类型表达二叉树结构的输入与输出的。

解决这道题，对我们在其他题目中构造与解析二叉树的输入输出用例都有很大帮助，推荐优先来做。

可以看出，leetcode 使用的序列化方式为广度优先遍历法。

至于这道题的解法就没有什么难点了，基础的 BFS 遍历算法，借助队列的方式存入当前节点的左右子节点，然后以先进先出的队列方式取的每次遍历的节点。

在 JS 这种动态语言里面天然支持一个数组或队列存在多种类型的值，而叶子节点的子节点的值天然为 null，这使得代码调试过程中不会有任何的阻碍。

但是 leetcode 的 js 解析器的实现上有点问题，貌似进行了一次强制类型转换，将 null, undefined 这种值转换为 0，使得解法不能 AC。因此，我们只能为了适配 leetcode 的 js 解析器，将判断 null 的值换为别的有实际意义的任何基础类型（本题解中为字符串'null')。

序列化时需要注意的点是，我们需要将序列化后的数组去除掉尾部的null值，这是因为在我们的遍历过程中，最后一个叶子节点的null子节点也被我们考虑进来了一次，而leetcode的实现上消去了这一点，我们也需要同步考虑上。

反序列化需要注意的点是，在遍历过程中要注意不要让数组的取值越界，这样会拿到不存在的节点。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var serialize = function(root) {
  if (!root) return '';
  const arr = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (!node) {
      arr.push('null');
      continue;
    }
    arr.push(node.val);

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

  // 去除尾部多余的 null
  while (arr.length >= 1 && arr[arr.length - 1] === 'null') arr.pop();

  return JSON.stringify(arr);
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
  if (data === '') return null;
  const arr = JSON.parse(data);
  const root = new TreeNode(arr[0]);
  const queue = [root];
  for (let i = 1; i < arr.length; i += 2) {
    const node = queue.shift();

    const leftNumber = arr[i];
    if (leftNumber !== 'null') {
      node.left = new TreeNode(leftNumber);
      queue.push(node.left);
    }

    const rightNumber = arr[i + 1];
    if (i + 1 < arr.length && rightNumber !== 'null') {
      node.right = new TreeNode(rightNumber);
      queue.push(node.right);
    }
  }
  return root;
};