297.二叉树的序列化与反序列化来源：LeetCodehttps://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree数据可以存储在文件或内存中，也可以通过网络传输到另一个计算机环境，采取相反的方式重构原始数据。请设计一个算法来实现二叉树的序列化和反序列化。这并不限制你的序列/反序列化算法执行逻辑，你只需要保证一个二叉树可以序列化成一个字符串，并将这个字符串反序列化成原来的树结构即可。示例：可以将如下二叉树：1/\23/\45序列化为“[1,2,3,null,null,4,5]”提示：这与LeetCode目前的做法一致，请参考参见LeetCode序列化二叉树的格式。你不一定要采用这种方法，你可以使用其他方法来解决这个问题。注意：不要使用类成员/全局/静态变量来存储状态，您的序列化和反序列化算法应该是无状态的。解题思路：深度优先搜索根据题目，我们可以理解。二叉树序列化其实就是将二叉树按照一定的遍历方式，按照一定的格式保存为字符串。在这篇文章中，我们使用的方法是使用深度优先搜索来达到这个目的。这里，我们使用深度优先搜索的思想，通过递归实现。在这个过程中，我们使用了前序遍历的方法来解决。当我们使用递归时，只需要关注单个节点，剩下的交给递归实现。使用前序遍历的原因是：前序遍历的访问顺序是先访问根节点，再遍历左子树，最后遍历右子树。这样我们第一次反序列化的时候就可以直接定位到根节点。这里有一点需要注意，当遇到空节点时，需要对其进行识别。这样在反序列化的时候就可以区分这是一个空节点。下面采用前序遍历的方法，借助示例1，以图的形式说明序列化过程：上图中，按照前序遍历的访问顺序，从根开始节点1，序列化字符为1。然后遍历左子树。此时左子树的根节点为2，序列化字符为1,2,.。此时从2开始，访问左节点(1,2,null,)，右节点(1,2,null,null)。这里的null就是上面提到的标记null的符号。这回到根节点，访问右子树。同样按照前序遍历的访问顺序，最终序列化后的字符串结果为：1,2,null,null,3,4,null,null,5,null,null,.至于如何反序列化？按照前序遍历的访问顺序规则，我们从左到右遍历序列化后的字符串：当当前元素为null时，为空树；当不存在上述情况时，先解析左子树，再解析右子树，具体实现代码如下。代码实现#Definitionforabinarytreenode.#classTreeNode(object):#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassCodec:defserialize(self,root):"""Encodesatreetoasinglestring.:typeroot:TreeNode:rtype:str"""如果root==None:return'null,'left_serialize=self.serialize(root.left)right_serialize=self.serialize(root.right)returnstr(root.val)+','+left_serialize+right_serializedefdeserialize(self,data):"""将编码数据解码为树。:typedata:str:rtype:TreeNode"""defdfs(queue):val=queue.popleft()ifval=='null':returnNonenode=TreeNode(val)node.left=dfs(queue)node.right=dfs(queue)returnnodefrom收藏进口tdequequeue=deque(data.split(','))returndfs(queue)#你的Codec对象将被实例化并这样调用：#codec=Codec()#codec.deserialize(codec.serialize(root))实现结果总结首先理解二叉树的序列化其实是基于某种遍历方式，使用dfs方式（也可以使用bfs）将结果保存为某种格式的字符串，而二进制tree按照前序遍历的访问方式进行序列化。这里采用了前序遍历的方式，也便于反序列化时快速定位到根节点。因为前序遍历的访问顺序是：先访问根节点，再遍历左子树，最后遍历右节点。序列化的时候，遇到None的时候，需要对其进行识别，这样反序列化的时候就可以区分为None和空树。反序列化，根据前序遍历的访问规则，拆分之前序列化的字符串，从左向右遍历：当元素为null时，表示空树；否则，先解析左子树，再解析右子树。
