297_二叉树的序列化与反序列化

难度：困难

题目

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例

示例一：

img

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

提示

  • 树中结点数在范围 [0, 10^4] 内
  • -1000 <= Node.val <= 1000

解题

可以对节点进行遍历，只要采用同一种遍历方式，就能保证序列化与反序列化一致

通过传递同一个 StringBuilder 对象来进行遍历，遇到 null 节点则 append null,,否则添加 node.val,。使用逗号分隔。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
  StringBuilder res = ser_help(root, new StringBuilder());
  return res.toString();
}

public StringBuilder ser_help(TreeNode root, StringBuilder str){
  if (root == null){
    str.append("null,");
    return str;
  }
  str.append(root.val);
  str.append(",");
  str = ser_help(root.left,str);
  str = ser_help(root.right,str);
  return str;
}

反序列化时，先将 String 转化为 List

1
2
String[] str_word = data.split(",");
List<String> list_word = new LinkedList<>(Arrays.asList(str_word));

然后按照先序遍历的顺序进行遍历，每次访问完都将访问过的元素移除，防止出错

1
2
3
4
5
6
7
8
9
10
11
public TreeNode deser_help(List<String> li){
  if (li.get(0).equals("null")){
    li.remove(0);
    return null;
  }
  TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));
  li.remove(0);
  res.left = deser_help(li);
  res.right = deser_help(li);
  return res;
}