当前位置: 首页 > news >正文

LeetCode297.二叉树的序列化和反序列化

题目要求

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

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

 

提示:

  • 树中结点数在范围 [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 "[]";}// 新建一个队列Queue<TreeNode> queue = new LinkedList<>();// 新建一个列表List<TreeNode> 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(",");// 构造队列Queue<TreeNode> 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;}
}


http://www.mrgr.cn/news/75188.html

相关文章:

  • SM软件加密与授权:构建安全高效的软件保护体系
  • SpringCloud学习笔记
  • 【数据库】深入解析慢 SQL 的识别与优化策略
  • AI 大模型应用:AI开发的捷径工作流模式
  • Qt 监控USB设备的插入和移除
  • SQL,力扣题目1107,每日新用户统计
  • 搜维尔科技:SenseGlove触觉反馈手套开箱+场景测试
  • IDL脚手架遇到的cwgo问题
  • 黑马智数Day8
  • 机器学习 ---模型评估、选择与验证(1)
  • cache中命中率和平均访问时间
  • RK3568平台开发系列讲解(platform虚拟总线驱动篇)platform总线模型
  • Shell脚本的使用
  • CPLD架构
  • KPaaS洞察|统一管理模式下跨系统用户权限修改流程详解
  • python进阶-01-利用Xpath来解析Html
  • 除自身以外数组的乘积
  • 关于GCC内联汇编(也可以叫内嵌汇编)的简单学习
  • 共享旅游卡项目深度解读,风险与机遇并存
  • Java 常见的面试题(Kafka)
  • 三天精通一种算法之移除数组元素(暴力)(快慢指针)
  • MySQL数据库:SQL语言入门 【2】(学习笔记)
  • Spring Security概述
  • 基于树莓派的日志抓取工具制作
  • 代理通讯链实现内网通讯
  • 探秘 RPC:揭开远程过程调用的实现原理