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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode题解：297. 二叉树的序列化与反序列化，BFS，JavaScript，详细注释，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2874字，纯文字阅读大概需要5分钟。

内容图文

原题链接：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));
 */

内容总结

以上是互联网集市为您收集整理的LeetCode题解：297. 二叉树的序列化与反序列化，BFS，JavaScript，详细注释全部内容，希望文章能够帮你解决LeetCode题解：297. 二叉树的序列化与反序列化，BFS，JavaScript，详细注释所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端