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.xdnf.cn/news/15710.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

蓝牙5.0模块助力闹钟升级,开启智能生活第一步

随着智能家居产业的快速发展&#xff0c;智能闹钟作为其中一个重要的品类&#xff0c;逐渐从单一的时间提醒功能演变为集音频播放、语音交互、智能控制等多种功能于一体的智能设备。而在这些功能的实现中&#xff0c;蓝牙音频模组扮演着核心角色。 1、蓝牙音频模组的功能概述 …

自己动手写Qt Creator插件

文章目录 前言一、环境准备1.先看自己的Qt Creator IDE的版本2.下载源码 二、使用步骤1.参考原本的插件2.编写自定义插件1.cmakelist增加一个模块2.同理&#xff0c;qbs文件也增加一个3.插件源码 三、效果总结 前言 就目前而言&#xff0c;Qt Creator这个IDE&#xff0c;插件比…

力扣经典面试题

1.本题的目标是判断字符串ransomNote是否由字符串magazine中的字符构成&#xff0c;且由magazine中的每个字符只能在ransomNote中使用一次 2.采用的方法是通过一个字典cahr_countl来统计magazine字符串中每个字符出现的次数 3.然后遍历ransomNote字符串&#xff0c;对于其中的…

Java开发人员从了学习ArkTs笔记(三)-数据结构与线程通信全解析

大家好&#xff0c;我是一名热爱Java开发的开发人员。目前&#xff0c;我正在学习ARKTS&#xff08;Advanced Java Knowledge and Technology Stack&#xff09;&#xff0c;并将不断输出我的学习笔记。我将在这里分享我学习ARKTS的过程和心得&#xff0c;希望能够为其他开发人…

Java基础——预定义类/自定义类封装什么是Final类型

目录 预定义类——日历输出&#xff1a; 自定义类——在Java文件中&#xff1a; 什么是封装&#xff1f; 什么是final类型&#xff1f; 修饰变量&#xff1a; 修饰方法&#xff1a; 修饰类&#xff1a; 预定义类——日历输出&#xff1a; 例如&#xff1a;Math类、Date类…

spi 回环

///tx 极性0 &#xff08;sclk信号线空闲时为低电平&#xff09; /// 相位0 (在sclk信号线第一个跳变沿进行采样) timescale 1ns / 1ps//两个从机 8d01 8d02 module top(input clk ,input rst_n,input [7:0] addr ,input …

20241114软考架构-------软考案例16答案

每日打卡题案例16答案 16.【2017年真题】 难度&#xff1a;简单 阅读以下关于软件架构评估的叙述&#xff0c;在答题纸上回答问题1和问题2.(共25分) 【说明】 某单位为了建设健全的公路桥梁养护管理档案&#xff0c;拟开发一套公路桥梁在线管理系统。在系统的需求分析与架构设…

低成本出租屋5G CPE解决方案:ZX7981PG/ZX7981PM WIFI6千兆高速网络

刚搬进新租的房子&#xff0c;没有网络&#xff0c;开个热点&#xff1f;续航不太行。随身WIFI&#xff1f;大多是百兆级网络。找人拉宽带&#xff1f;太麻烦&#xff0c;退租的时候也不能带着走。5G CPE倒是个不错的选择&#xff0c;插入SIM卡就能直接连接5G网络&#xff0c;千…

Python学习小记3-传递任意数量的实参

1.形参名*toppings 中的星号让Python创建一个名为toppings 的空元组&#xff0c;不管调用语句提供了多少实参&#xff0c;这个形参会将它们统统收入囊中&#xff0c;即&#xff1a;无论几个小料 def make_pizza(size, *toppings):print(f"\n要制作一个{size}-inch的披萨&…

宝塔 docker 部署onlyoffice 服务

1.宝塔安装docker,直接下载安装就行 2.docker拉取onlyoffice镜像 docker pull onlyoffice/documentserver:5.3.1.26 5.4或更高的版本已经解决了连接数限制方法的Bug 3.创建容器 docker run -d --name onlyoffice --restartalways -p 暴露端口号:80 onlyoffice/documentserv…

【数据结构副本篇】顺序表 链表OJ

&#x1f3dd;️专栏&#xff1a;【数据结构实战篇】 &#x1f305;主页&#xff1a;f狐o狸x 学习其实和打游戏一样&#xff0c;当你觉得BOSS难打的时候就说明是你的等级和装备不够&#xff0c;此时就需要我们多去刷刷副本&#xff0c;增加一点经验&#xff0c;顺便爆点装备出…

论文笔记(五十六)VIPose: Real-time Visual-Inertial 6D Object Pose Tracking

VIPose: Real-time Visual-Inertial 6D Object Pose Tracking 文章概括摘要I. INTRODACTIONII. 相关工作III. APPROACHA. 姿态跟踪工作流程B. VIPose网络 文章概括 引用&#xff1a; inproceedings{ge2021vipose,title{Vipose: Real-time visual-inertial 6d object pose tra…

AI风向标|算力与通信的完美融合,SRM6690解锁端侧AI的智能密码

当前&#xff0c;5G技术已经成为推动数字经济和实体经济深度融合的关键驱动力&#xff0c;进入5G发展的下半场&#xff0c;5G与AI的融合正推动诸多行业的数字化转型和创新发展&#xff0c;终端侧AI和端云混合式AI将广泛应用于各类消费终端和各行各业。 在推动5G和AI与各行业场…

封装一个省市区的筛选组件

筛选功能&#xff1a;只能单选&#xff08;如需多选需要添加show-checkbox多选框属性&#xff09;&#xff0c;选中省传递省的ID&#xff0c;选中市传递省、市的ID&#xff0c; 选中区传递省市区的ID 父组件&#xff1a; <el-form-item><div style"width: 240px;…

Liunx:共享内存

共享内存是实现进程间通信的又一个策略。 与管道在逻辑上相似&#xff0c;用户可以向OS申请&#xff0c;在物理内存中开辟一块空间&#xff0c;OS开辟并向上层返回这块空间的起始地址。需要通信的双方将这块空间通过页表映射&#xff0c;各自的挂载到自己进程地址空间的共享区。…

STM32 创建一个工程文件(寄存器、标准库)

首先到官网下载对应型号的固件包&#xff1a; 像我的STM32F103C8T6的就下载这个&#xff1a; 依次打开&#xff1a; .\STM32F10x_StdPeriph_Lib_V3.5.0\STM32F10x_StdPeriph_Lib_V3.5.0\Libraries\CMSIS\CM3\DeviceSupport\ST\STM32F10x\startup\arm 可以看到&#xff1a; 这…

鸿蒙HarmonyOS 地图不显示解决方案

基于地图的开发准备已完成的情况下&#xff0c;地图还不显式的问题 首先要获取设备uuid 获取设备uuid 安装DevEco Studio的路径下 有集成好的hdc工具 E:\install_tools\DevEco Studio\sdk\default\openharmony\toolchains 这个路径下打开cmd运行 进入“设置 > 关于手机…

主机型入侵检测系统(HIDS)——Elkeid在Centos7的保姆级安装部署教程

一、HIDS简介 主机型入侵检测系统(Host-based Intrusion Detection System 简称:HIDS);HIDS作为主机的监视器和分析器,主要是专注于主机系统内部(监视系统全部或部分的动态的行为以及整个系统的状态)。 HIDS使用传统的C/S架构,只需要在监测端安装agent即可,且使用用户…

ArkUI---使用弹窗---@ohos.promptAction (弹窗)

promptAction.showToast&#xff08;文本提示框&#xff09; showToast(options: ShowToastOptions): void 创建并显示文本提示框&#xff0c;想看官方文档请点我 ShowToastOptions相关参数请点我 完整代码&#xff1a; import { promptAction } from kit.ArkUIEntry Componen…

leetcode104:二叉树的最大深度

给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3示例 2&#xff1a; 输入&#xff1a;root [1,null,2] 输出…