芍药居网站建设公司,wordpress首页文章摘要,蚌埠高端网站建设,h5页面制作工具是什么题目要求
序列化是将一个数据结构或者对象转换为连续的比特位的操作#xff0c;进而可以将转换后的数据存储在一个文件或者内存中#xff0c;同时也可以通过网络传输到另一个计算机环境#xff0c;采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序…题目要求
序列化是将一个数据结构或者对象转换为连续的比特位的操作进而可以将转换后的数据存储在一个文件或者内存中同时也可以通过网络传输到另一个计算机环境采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示
树中结点数在范围 [0, 104] 内-1000 Node.val 1000 解题思路
观察可知二叉树的序列化和反序列化都是通过二叉树的层序遍历进行实现的所以我们想要解题就要通过二叉树的层序遍历的性质来进行解题。
遍历数组当1个节点进入队列的时候且弹出该节点之时则当前处理的该节点算是一个根节点。按照层序遍历的特点我们设有一个i指针。
当弹出节点的时候i正好位于当前节点的左子结点。i自增1之后则i处于当前根节点的右子节点中。若非空则子节点加入栈。
代码解析
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val x; }* }*/
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if (root null){return [];}// 新建一个队列QueueTreeNode queue new LinkedList();// 新建一个列表ListTreeNode list new ArrayList();// 根节点入队queue.offer(root);while (!queue.isEmpty()) {TreeNode node queue.poll();if (node ! null) {list.add(node);queue.offer(node.left);queue.offer(node.right);} else {list.add(null);}}StringBuilder sb new StringBuilder();sb.append([);sb.append(list.stream().map(node - node null ? null : String.valueOf(node.val)).collect(Collectors.joining(,)));sb.append(]);String result sb.toString();return result;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if (data.equals([])) {return null;}// 构造值数组String[] vals data.substring(1, data.length() - 1).split(,);// 构造队列QueueTreeNode queue new LinkedList();// 构造根节点TreeNode root new TreeNode(Integer.parseInt(vals[0]));// 根节点加入队列queue.offer(root);int i 1;while (!queue.isEmpty()) {// 弹出当前根节点TreeNode curRoot queue.poll();if (!vals[i].equals(null)) {curRoot.left new TreeNode(Integer.parseInt(vals[i]));queue.offer(curRoot.left);}i;if (!vals[i].equals(null)) {curRoot.right new TreeNode(Integer.parseInt(vals[i]));queue.offer(curRoot.right);}i;}return root;}
}
