题目(序列化二叉树—牛客网)

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

算法思路

总体思路是利用前序遍历进行序列化和反序列化，但是我们知道仅有前序遍历是无法确定一颗二叉树的，所以我们还需要要给叶节点的空指针赋予特殊的标记 ‘#’，这样一来，当递归遇到’#’时，我们就知道了该跳出递归了，回溯完之后就进入右子树处理了。另外，二叉树的节点值可能有两位数，这样就不能单靠指针的移动就能确定二叉树的节点值，还需要加入分割标记，因此我们序列化的时候，需额外追加逗号，分割开不同的二叉树节点值，方便反序列化取出节点值。

处理思路一

借助整形类型的vector数组存储二叉树节点值，所以我们进行序列化的时候，对二叉树进行前序遍历(或称DFS)将节点加入数组，当节点为空的时候，加入特殊值 0x23333，并退出递归。但由于函数需要返回字符数组类型，因此还需要将vector数组中的元素一一复制到动态整形数组中，最后对整形数组强制类型转为字符类型。
反序列化时，先将字符数组类型强制类型转为整形数组，然后二叉树节点的值就可以直接从整形数组中得到。首先，处理递归出口，如果遇到 ox23333，则指针移动一个单位并退出递归。否则构造二叉树根节点，并继续移动指针，连接递归得到的左子树，以及右子树。

处理思路二

借助string类型的变量来拼接序列化的字符串。只需前序遍历二叉树，当遇到根节点为空时，追加 ‘#’，并退出递归，否则追加二叉树的根节点值，接着追加逗号。接下只需递归实现左子树和右子树的序列化。那么，序列化之后得到了string类型的字符串，最后构造动态字符数组，将字符串的每一个字符复制到字符数组中，结尾加入’\0’标记结束。
进行反序列化时，如果遇到 ‘#’ ，那么指针移动一个单位，退出递归。否则，找到字符数组中的一个二叉树节点值，然后构造根节点，如果此时到达字符末尾，直接返回根节点，否则指针继续移动一个单位。接下来根节点的左右指针分别连接左子树的递归实现结果和右子树的递归实现结果。

算法实现

算法实现一

算法实现二

参考

[1]. <<剑指offer2>>
[2]. <<牛客网>>