剑指 Offer 37. 序列化二叉树
本问题对应的 leetcode 原文链接：剑指 Offer 37. 序列化二叉树
本问题对应打卡任务：【二叉树专题】剑指 Offer 37. 序列化二叉树
问题描述
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
解题思路
视频讲解直达： 本题视频讲解
代码实现
序列化：
时间复杂度：O(n)
额外空间复杂度：O(n)
反序列化：
时间复杂度：O(n)
空间复杂度：O(n)
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if(root == null){
return "";
}
StringBuilder build = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
if(t != null){
queue.add(t.left);
queue.add(t.right);
build.append(t.val + ",");
}else{
build.append("null,");
}
}
return build.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// 1,2,3,null,null,4,5,null...
if(data == null || data.length() <= 0){
return null;
}
String[] s = data.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
queue.add(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode t = queue.poll();
// 构建做左节点
if(!s[i].equals("null")){
TreeNode left = new TreeNode(Integer.parseInt(s[i]));
t.left = left;
queue.add(left);
}
i++;
// 构建右节点
if(!s[i].equals("null")){
TreeNode right = new TreeNode(Integer.parseInt(s[i]));
t.right = right;
queue.add(right);
}
i++;
}
return root;
}
}