61-序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

分析

首先拿到题目时候，我先想到的是什么是序列化二叉树？序列化主要就是在前后端交互时候需要转换下，毕竟网络传输的是流式数据（二进制或者文本），而不是对象。

所以序列化二叉树就是转化成字符串。

之前解决重建二叉树问题时候，我们可以知道，两个遍历序列就可以确定一颗二叉树。（比如前序遍历序列和中序遍历序列）。

受此启发，序列化时候我们可以生成一个前序遍历序列和一个中序遍历序列，在反序列化时通过这两个序列重构出原二叉树。

但是当我们细细想下，这个思路有两个个缺点就是：

1.如果二叉树有数值重复的节点，那么必须区分谁是前序遍历序列，谁是后序遍历序列。

2.只有当两个序列所有数据读出后才能开始反序列化。

因此我们可以想，既然是可以边读，边构建二叉树，你是不是想到了自己平时如何构建二叉树的？

我们可以通过深度遍历或者广度遍历序列都行，当然我们最终选择了深度优先遍历，毕竟可以不用额外的空间。

此外还有个技巧就是为了更好地知道遍历某个子树的结束，也就是当我们遍历到null时，我们需要用换位符（比如$）代表，方便反序列化。

此外，我尝试过用字符串做发现不好做，然后转变了下思路，用数组来模拟流，发现就好做了很多。

此外，利用反序列化，我们可以通过数组很快的生成我们想要的二叉树，然后拿去做测试，毕竟一个一个的创建节点，生成二叉树太傻了

代码

const arr = [];
function Serialize(pRoot) {
  // write code here
  if (pRoot === null) {
    arr.push('a');
  } else {
    arr.push(pRoot.val);
    Serialize(pRoot.left);
    Serialize(pRoot.right);
  }
}
function Deserialize() {
  // write code here
  let node = null;
  if (arr.length < 1) {
    return null;
  }
  const number = arr.shift();
  if (typeof number === 'number') {
    node = new TreeNode(number);
    node.left = Deserialize();
    node.right = Deserialize();
  }
  return node;
}