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

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

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

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

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

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

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

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

思路

用BFS 和 栈的结构特性来进行序列化和反序列化

代码

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
  if (!root) return '[]';
    let queue = [], res = []
    queue.push(root)
    while(queue.length) {
      let curLevel = queue
      queue = []
      for(let i = 0; i < curLevel.length; i ++) {
        let cur = curLevel[i]
        if (cur !== null) {
          res.push(cur.val)
          queue.push(cur.left)
          queue.push(cur.right)
        } else {
          res.push(null)
        }
      }
    }
    // while(!res[res.length - 1]) {
    //   res.pop()
    // }
    return JSON.stringify(res)
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    data = JSON.parse(data)
    if (!data.length) {
      return null
    }
    // console.log(data)
    let root = new TreeNode(data[0])
    let queue = [root], i = 1, len = data.length
    while(queue.length && i < len) {
      let node = queue.shift()
      if (data[i] !== null) {
        node.left = new TreeNode(data[i])
        queue.push(node.left)
      }
      i += 1;
      if (data[i] !== null) {
        node.right = new TreeNode(data[i])
        queue.push(node.right)
      }
      i += 1;
    }
    return root
};

复杂度分析

时间复杂度 $O(N)$ $O(N)$

空间复杂度 $O(N)$ $O(N)$