题目描述

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

 

题目分析

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

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

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

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

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

　　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;}