asp网站开发教案,有没有什么东西可以做网站,WordPress允许用户修改评论,沈阳专业网站建设企业297.二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作#xff0c;进而可以将转换后的数据存储在一个文件或者内存中#xff0c;同时也可以通过网络传输到另一个计算机环境#xff0c;采取相反方式重构得到原数据。
请设计一个算法来实现…297.二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式你也可以采用其他的方法解决这个问题。
示例 1
输入root [1,2,3,null,null,4,5]
输出[1,2,3,null,null,4,5]示例 2
输入root []
输出[]示例 3
输入root [1]
输出[1]示例 4
输入root [1,2]
输出[1,2]提示
树中结点数在范围 [0, 104] 内-1000 Node.val 1000
题解
这道题涉及到了二叉树的序列化与反序列化由于序列化和反序列化的操作必须是可逆的因此必须将完整的二叉树序列化(就是将叶子节点下面的节点也都序列化出来序列化成两个null)这样反序列化之后的树才能是唯一的。以示例一来举例。
将示例一的输入序列化之后得到的结果是这样的。
1,2,3,null,null,4,5,null,null,null,null可以使用BFS的思想来层序遍历取出各个元素来生成这个字符串这部分的思路类似于这题二叉树的层序遍历。
代码实现如下
public static String serialize(TreeNode root) {if (root null) {return ;}QueueTreeNode queue new ArrayDeque();queue.add(root);StringBuilder sb new StringBuilder();while (!queue.isEmpty()) {TreeNode node queue.poll();if (node.val NULL) {sb.append(null);sb.append(,);continue;}else {sb.append(node.val);sb.append(,);}if (node.left ! null) {queue.add(node.left);}else {queue.add(new TreeNode(NULL));}if (node.right ! null) {queue.add(node.right);}else {queue.add(new TreeNode(NULL));}}return sb.substring(0, sb.length() - 1);
}序列化完成之后就可以考虑反序列化的问题了我们先将序列化之后的String按照,分割成一个String数组这里的难点在于如何定位到当前节点的值在序列化之后的String中的位置。
感觉有点规律但是又不知道规律在哪可以画图如下所示。 图中-左边的数字表示这个节点的值在序列化之后的数组中的index右边的数字表示这个节点的值。
通过观察可以发现每个节点的两个叶子节点的index可以根据父节点的index计算出来如下。
leftIndex 2 * index 1;
rightIndex 2 * index 2;因此可以按照序列化同样的逻辑来进行反序列化使用BFS。
代码实现如下
package com.offer;import com.jvm.jad.T;
import com.offer.leetcode.datastruct.TreeNode;
import com.springAnnotation.pojo.A;
import com.缺失的第一个正数;
import sun.reflect.generics.tree.Tree;import java.util.*;public class _297二叉树的序列化与反序列化 {public static void main(String[] args) {TreeNode root new TreeNode(1);root.left new TreeNode(2);root.right new TreeNode(3);TreeNode r root.right;r.left new TreeNode(4);r.right new TreeNode(5);System.out.println(serialize(root));System.out.println(deserialize(serialize(root)));}private static int NULL -1001;// Encodes a tree to a single string.public static String serialize(TreeNode root) {if (root null) {return ;}QueueTreeNode queue new ArrayDeque();queue.add(root);StringBuilder sb new StringBuilder();while (!queue.isEmpty()) {TreeNode node queue.poll();if (node.val NULL) {sb.append(null);sb.append(,);continue;}else {sb.append(node.val);sb.append(,);}if (node.left ! null) {queue.add(node.left);}else {queue.add(new TreeNode(NULL));}if (node.right ! null) {queue.add(node.right);}else {queue.add(new TreeNode(NULL));}}return sb.substring(0, sb.length() - 1);}// Decodes your encoded data to tree.public static TreeNode deserialize(String data) {if (.equals(data)) {return null;}String[] nodeVals data.split(,);TreeNode root new TreeNode(Integer.parseInt(nodeVals[0]));int index 0;QueueTreeNode queue new ArrayDeque();queue.add(root);while (!queue.isEmpty()) {TreeNode node queue.poll();index;String val nodeVals[2 * index 1];if (!null.equals(val)) {node.left new TreeNode(Integer.parseInt(val));queue.add(node.left);}val nodeVals[2 * index 2];if (!null.equals(val)) {node.right new TreeNode(Integer.parseInt(val));queue.add(node.right);}}return root;}
}
