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

链接：297.二叉树的序列化与反序列化
难度：Hard
标签：树、深度优先搜索、广度优先搜索、设计、字符串、二叉树
简介：请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

题解 1 - javascript

• 编辑时间：2020-06-16
• 执行用时：108ms
• 内存消耗：44MB
• 编程语言：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}
 */
var serialize = function (root) {
  return root;
};
/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  return data;
};
/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

题解 2 - javascript

• 编辑时间：2020-06-16
• 执行用时：156ms
• 内存消耗：46.8MB
• 编程语言：javascript
• 解法介绍：使用 LeetCode 格式进行序列化与反序列化。

var serialize = function (root) {
  const queue = [root];
  let str = '';
  while (!isNull()) {
    const node = queue.shift();
    if (node === null) {
      str += 'null,';
      continue;
    } else {
      str += node.val + ',';
    }
    if (node.left !== null) queue.push(node.left);
    else queue.push(null);
    if (node.right !== null) queue.push(node.right);
    else queue.push(null);
  }
  return `[${str.substr(0, str.length - 1)}]`;
  function isNull() {
    for (const node of queue) {
      if (node !== null) return false;
    }
    return true;
  }
};
var deserialize = function (data) {
  if (data === '[]') return null;
  const arr = data
    .substring(1, data.length - 1)
    .split(',')
    .map(v => (v === 'null' ? null : Number(v)));
  if (arr.length === 0) return null;
  let root = new TreeNode(arr.shift());
  const queue = [root];
  while (queue.length !== 0) {
    const node = queue.shift();
    let temp = arr.shift();
    if (temp !== null && temp !== undefined) {
      node.left = new TreeNode(temp);
      queue.push(node.left);
    }
    temp = arr.shift();
    if (temp !== null && temp !== undefined) {
      node.right = new TreeNode(temp);
      queue.push(node.right);
    }
  }
  return root;
};

题解 3 - typescript

• 编辑时间：2021-06-30
• 执行用时：152ms
• 内存消耗：48.1MB
• 编程语言：typescript
• 解法介绍：利用 JSON 化。

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  return JSON.stringify(root);
};
/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  return JSON.parse(data);
};