题目大意：
二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=297
解题思路分析：
经常看我博客的朋友应该了解，解决二叉树问题最好的办法即是使用dfs或者bfs来解题。本题也不例外，我们以dfs为例来讲解。
使用dfs遍历树形结构时，不论是用先序，中序还是后续遍历都不会影响我们解题。序列化二叉树时，我们使用一个String来表示序列化后的字符串。dfs方法中，首先判断当前节点是否为空，如果为空，我们可以在序列化字符串中拼接一个null字符串来表明。反之，我们将当前节点的数值拼接到到序列化字符串中，接下来，我们dfs递归至左子节点，将左子节点序列化后（dfs递归返回值）的字符串拼接到当前字符串尾部，然后再dfs至右子节点，同理再将右子节点序列化后的字符串拼接到当前字符串中。最后当前拼接完成的字符串即是当前dfs方法的返回值。另外为了区分每个节点，我们可以使用一个逗号来隔开每个节点的数值。
反序列化时同样需要使用到dfs，理论上我们使用序列化的递归顺序来反序列化即可。首先我们先将序列化后的字符串以逗号分隔成数组，为了方便使用，我们可以使用一个Queue来存储所有分隔好的节点值。接下来dfs开始！dfs方法中，首先从queue中取出一个元素，如果该元素为字符串”null”，代表该节点为空，返回空对象即可。如果不为”null”，那么这是二叉树中的一个节点，我们使用节点的构造方法new出一个节点对象，该对象的值为当前数值。接下来，当前节点的左子节点和右子节点对象可以分别通过dfs递归取得，注意，dfs递归的执行循序要与序列化时的顺序一致，即先dfs一次，返回结果是左子节点对象，第二次dfs的结果是右子节点对象。最后，当前dfs方法的返回值为当前节点对象。
最后为了优化程序，在序列化拼接字符串时，我们可以考虑使用StringBuilder来取代String。
实现代码：
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return dfs(root).toString(); // dfs序列化二叉树
}
// dfs序列化二叉树
StringBuilder dfs(TreeNode root){
StringBuilder sb = new StringBuilder(); // 序列化后字符串
if(root==null){ // 如果当前节点为空，向字符串后拼接一个null字符串
sb.append("null,");
}else{ // 当前节点不为空
sb.append(root.val).append(","); // 首先拼接当前字符串数值
sb.append(dfs(root.left)); // 将左子节点的序列化字符串拼接到当前字符串后
sb.append(dfs(root.right)); // 将右子节点的序列化字符串拼接到当前字符串后
}
return sb; // 返回当前拼接后的字符串
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// 将所有节点值以逗号分隔，并存至Queue中
Queue<String> q=new LinkedList<>(Arrays.asList(data.split(",")));
// dfs反序列化
return dfs(q);
}
// dfs反序列化
TreeNode dfs(Queue<String> q){
String val=q.poll(); // 取出一个节点数值
// 如果当前数值为null，返回空对象
if("null".equals(val)) return null;
else{ // 当前节点不为空
// 利用当前节点数值新建一个节点对象
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left=dfs(q); // 左子节点对象为dfs后的返回值
node.right=dfs(q); // 右子节点对象为第二次dfs后的返回值
return node;
}
}本题解法执行时间为10ms。
Runtime: 10 ms, faster than 75.34% of Java online submissions for Serialize and Deserialize Binary Tree.
Memory Usage: 41.3 MB, less than 73.13% of Java online submissions for Serialize and Deserialize Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-297-serialize-and-deserialize-binary-tree-解题思路分析/