前言有一颗二叉树，将其按照特定的规则转化为字符串称为序列化，将序列化后的字符串按照序列化的规则恢复为二叉树称为反序列化。那么如何实现二叉树和字符串的转换呢？本文将与您分享解决此问题的方法。欢迎所有感兴趣的开发者阅读本文。实现思路在ReconstructingaBinaryTree一文中，我们学习了使用前序遍历序列和中序遍历序列将字符串构建成二叉树。这种思路有两个缺点：二叉树中不能有重复值的节点，反序列化只能在两个序列中的数据全部读出后才能开始（如果两个序列中的数据都是从一个流中读取的，那么你需要比老师等的时间更长）其实我们在使用前序遍历读取二叉树的时候，得到的序列是从根节点开始的，所以反序列化可以在根节点读完之后开始。当我们在序列化的时候可能会遇到一个空节点，我们用一个特殊的字符（比如“$”）来标记它。节点值之间的连接也需要用特殊字符（如“，”）来标记。序列化规则明确后，我们举个例子来验证一下是否可行，如下图（一棵二叉树）：根据上面定义的规则，我们使用前序遍历得到的序列为：1,2,4,$,$,$,3,5,$,$,6,$,$。经验证，上述方法成功实现了树的序列化。下面我们以字符串1,2,4,$,$,$,3,5,$,$,6,$,$为例分析二叉树如何反序列化。读取的第一个数字是1，由于前序遍历是从根节点开始的，所以这是根节点的值。紧接着读到的数是2，按照先序遍历的规则，就是根节点的左子节点的值。同样，下一个数字4是值为2的节点的左孩子。然后从序列化后的字符串中读取两个字符“$”，表示节点4的左右孩子节点均为空，所以是叶子节点。接下来回到节点2并重建它的右孩子。继续读字符，下一个字符是“$”，表示节点2的右子节点为空。该节点的左右子树已经构建完成。接下来返回根节点，反序列化根节点的右子树。下一个序列化字符串中读取的数字是3，所以根节点右子树的值为3。它的左孩子是值为5的叶节点，因为接下来的三个字符是“5,$,$”。同样，它的右子节点是一个值为6的叶节点，因为最后3个字符是“6,$,$”。字符串中的所有字符都读取完毕，序列化过程结束，重建树，如下图（分析思路时画的辅助线去掉）。经过前面的分析，我们已经得到了一个完整的Idea，接下来我们看一下代码的实现。序列化二叉树我们可以使用前序遍历来完成二叉树的序列化。publicserialize(root:BinaryTreeNode|null):string{//空节点用$表示if(root==null)return"$";const结果：serializeNode={nodeVal:""};this.serializeFn(根,结果);//末尾会有多余的分隔符，去掉它们returnresult.nodeVal.substring(0,result.nodeVal.length-1);}/***处理树序列化的实现函数*@paramroot树根节点*@paramstrObj序列化节点对象*@private*/privateserializeFn(root:BinaryTreeNode|null|undefined,strObj:serializeNode){if(root==null){strObj.nodeVal+="$,";返回;}strObj.nodeVal+=root.key+",";this.serializeFn(root.left,strObj);this.serializeFn(root.right,strObj);}反序列化的时候我们在序列化的时候用到了前序遍历，反序列化的时候也要用到同样的前序遍历。反序列化的时候有点麻烦，需要先把字符串中的每个字符放到数组中。那么按照我们之前的分析：定义一个全局变量cross表示当前读取的字符数（步长），递归执行构造函数时，步长会先递增。根节点的左子树一定是紧跟根之后的字符，所以从index+1的位置继续执行递归函数，直到遇到“$”字符。根节点的右子树必须紧跟在它的左子树字符之后，所以从交叉位置继续执行递归函数，直到遇到“$”字符。根节点的左右子树构建完成后，返回构建的根节点，得到一棵完整的树/***反序列化二叉树*@paramtreeStr*/publicdeserialize(treeStr:string):BinaryTreeNode|空{如果(treeStr==="$"){返回空;}返回this.deserializeFn(treeStr);}/***处理树的反序列化实现函数*@paramnodeStrVal反序列化后的树节点String*@private*/privatedeserializeFn(nodeStrVal:string){//读取字符串的每个字符并转换为数组conststrArr:数组<字符串>=[];让readIndex=0;while(readIndex
