请实现两个函数,分别用来序列化和反序列化二叉树。 您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。 数据范围 树中节点数量 [0,1000]。 样例 你可以序列化如下的二叉树 8 / \ 12 2 / \ 6 4 为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]" 注意: 以上的格式是AcWing序列化二叉树的方式,你不必一定按照此格式,所以可以设计出一些新的构造方式。
时间: 2024-02-26 08:56:36 浏览: 64
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
以下是Java实现:
```java
public class Solution {
public String serialize(TreeNode root) {
if (root == null) {
return "null,";
}
String res = root.val + ",";
res += serialize(root.left);
res += serialize(root.right);
return res;
}
public TreeNode deserialize(String data) {
String[] dataArray = data.split(",");
Queue<String> queue = new LinkedList<>(Arrays.asList(dataArray));
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals("null")) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
}
```
其中,serialize函数用于将二叉树序列化为字符串,deserialize函数用于将字符串反序列化为原始树结构。具体实现方式如下:
1. 对于空节点,序列化为字符串"null,",表示该节点为空。
2. 对于非空节点,序列化为字符串"val,",其中val为节点的值。
3. 对于反序列化,我们使用一个队列来存储字符串的每一个元素。首先从队列中取出一个元素val,如果val为"null",则返回null;否则,创建一个新节点,并递归构建其左子树和右子树。
需要注意的是,在序列化时,我们使用递归的方式遍历整棵树;在反序列化时,我们使用队列来模拟先序遍历的过程。
阅读全文