LeetCode题解：297. 二叉树的序列化与反序列化，BFS，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

解题思路：

1. 参考了『手画图解』剖析DFS、BFS解法 | 二叉树的序列化与反序列化。
2. 该题实际上并没有严格的要求将二叉树序列化为[1,2,3,null,null,4,5]的形式，只要能够输出为1,2,X,X,3,4,X,X,5,X,X（X表示节点为null），并且重新反序列化为二叉树即可。
3. 序列化：
   • 使用BFS遍历每个节点，将遍历到的值都存在数组serialized中。
   • 如果遇到节点为空，则将X存入serialized。
   • 如果节点有值，则将节点的值存入serialized，同时将左右子树存入queue，这样就保证了serialized中是按照根、左、右的顺序存储值。
   • 最后将serialized转化为字符串返回即可。
4. 反序列化：
   • 由于已经按照根、左、右的顺序，对二叉树进行了序列化，只要按照这个顺序，使用队列queue生成二叉树即可。
   • 将序列化的字符串转换成数组valList，每次循环从valList中出队两个值，分别为左右子节点的值。如果值存在，就用其创建一个节点。
   • 从valList中出队的同时，从queue中出队一个节点，将其和左右子节点相连接。
   • 当valList中元素被清空时，表示二叉树已经生成完毕。

/**
 * 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}
 */
var serialize = function (root) {
  let queue = [root]; // 使用队列遍历二叉树
  let serialized = []; // 用数组存储序列化后的值

  // 队列被清空时，表示完成了二叉树的遍历
  while (queue.length) {
    // 缓存当前一行的节点数量
    let queueLength = queue.length;

    // 将当前一行的节点出队，进行处理
    for (let i = 0; i < queueLength; i++) {
      const node = queue.shift();

      if (node) {
        // 如果当前节点不为null，将其值存入serialized
        serialized.push(node.val);
        // 将左右子节点存入队列，供下一行遍历处理
        // 队列中的节点，总是保持根、左、右的顺序排列
        queue.push(node.left, node.right);
      } else {
        // 如果当前节点为null，将X存入serialized
        serialized.push('X');
      }
    }
  }

  // 将数组转换成字符串返回
  return serialized.join(',');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  // 如果根节点为null，那么data为X，直接返回null即可
  if (data === 'X') {
    return null;
  }

  // 将data转换为数组方便依次处理
  const valList = data.split(',');
  // 从数组中出队根节点的值，创建一个根节点
  const root = new TreeNode(valList.shift());
  // 将根节点存入队列，使用队列辅助创建二叉树
  let queue = [root];

  // valList被清空，表示所有值都已用来创建二叉树
  while (valList.length) {
    // 从队列中出队一个节点
    const node = queue.shift();
    // 因为valList中的值都是按照根、左、右排列，所以可以从valList连续出队左右子节点的值
    const left = valList.shift();
    const right = valList.shift();

    // 如果值不为空，就创建一个节点
    // 此时意味着valList还存有其子节点的值，此时只需要将节点存入queue，即可在下一次循环中处理
    if (left !== 'X') {
      node.left = new TreeNode(left);
      queue.push(node.left);
    }
    if (right !== 'X') {
      node.right = new TreeNode(right);
      queue.push(node.right);
    }
  }

  // 将生成的二叉树根节点返回即可
  return root;
};

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