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

Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】

题目

请实现两个函数,分别用来序列化和反序列化二叉树。

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

提示:输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

示例:

输入:root = [1,2,3,null,null,4,5]
输出:[1,2,3,null,null,4,5]

 

解题思路

1.题目要求我们实现两个函数,分别用来序列化和反序列化二叉树。首先我们来实现序列化二叉树,也就是将二叉树的层序遍历变为一个数组,那我们就需要用一个StringBuilder (res)来拼接遍历到的元素,还需要一个队列 queue 来按照层序遍历来遍历二叉树,首先我们将根节点放入 queue 中,当 queue不为null,我们就让queue中的元素出队,然后判断当前出队元素是否为null,若当前出队元素不为null,我们就将当前出队元素与“,”(逗号)拼接到 StringBuilder (res)中,然后再将当前出队元素的左右孩子加入队列中。若当前出队元素为 null,我们就将 “null,”拼接到 queue 中。最后我们将多余的“,”删除,并且加上“]”,然后返回即可。

2.反序列化的实现有一点复杂我们画图来看,

举个例子:

 实现反序列化我们依旧需要一个队列 queue,然后将所给的数组去除逗号后将它保存在数组vals中,我们知道层序遍历的第一个元素是二叉树的根节点,所以我们先让 vals[0] 入队。同时设置一个变量i = 1(遍历数组用)。

 当队列queue不为null时,我们让队头元素出列(2出列),这时 i 指向的元素不为 null 恰好是(2)的左孩子,所以我们就要令(2) 的左孩子指向(3),并且让(3)入队。然后我让 i 后移一位,

 这时 i 指向的元素不为 null 恰好是(2)的右孩子,所以我们就要令(2) 的右孩子指向(4),并且让(4)入队。然后我让 i 后移一位,

 queue不为null,我们让队头元素出列(3出列),这时 i 指向的元素不为 null 恰好是(3)的左孩子,所以我们就要令(3) 的左孩子指向(5),并且让(5)入队。然后我让 i 后移一位,

 这时 i 指向的元素为 null ,我们不做任何操作,因为(3)的右孩子(node.right)初始值就为null,我直接将 i 后移一位,

 queue不为null,我们让队头元素出列(4出列),这时 i 指向的元素不为 null 恰好是(4)的左孩子,所以我们就要令(4) 的左孩子指向(6),并且让(6)入队。然后我让 i 后移一位, 

 i 指向的元素为 null ,我们不做任何操作,接将 i 后移一位,

 queue不为null,我们让队头元素出列(5出列), i 指向的元素为 null ,我们不做任何操作,接将 i 后移一位,

 i 指向的元素为 null ,我们不做任何操作,接将 i 后移一位,

  queue不为null,我们让队头元素出列(6出列), i 指向的元素为 null ,我们不做任何操作,接将 i 后移一位,

  i 指向的元素为 null ,我们不做任何操作,接将 i 后移一位,

代码实现

public class Codec {public String serialize(TreeNode root) {if(root == null) return "[]";StringBuilder res = new StringBuilder("[");Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};while(!queue.isEmpty()) {TreeNode node = queue.poll();if(node != null) {res.append(node.val + ",");queue.add(node.left);queue.add(node.right);}else res.append("null,");}res.deleteCharAt(res.length() - 1);res.append("]");return res.toString();}// 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(",");TreeNode root = new TreeNode(Integer.parseInt(vals[0]));Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};int i = 1;while(!queue.isEmpty()) {TreeNode node = queue.poll();if(!vals[i].equals("null")) {node.left = new TreeNode(Integer.parseInt(vals[i]));queue.add(node.left);}i++;if(!vals[i].equals("null")) {node.right = new TreeNode(Integer.parseInt(vals[i]));queue.add(node.right);}i++;}return root;}
}

测试结果

 

相关文章:

Leetcode-每日一题【剑指 Offer 37. 序列化二叉树】

题目 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑&#xff0c;你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 …...

删除无点击数据offer数据分析使用

梳理思路&#xff1a; 1、 获取 7month 和 8month fullreport 报表中 所有offer&#xff1b;输出结果&#xff1a;offerid&#xff0c; totalClickCount&#xff1b; 2、 分析数据7month totalClickCount0 and 8month totalClickCount0 的offer去除&#xff1b; result.…...

【Apollo学习笔记】——规划模块TASK之SPEED_BOUNDS_PRIORI_DECIDER

文章目录 前言SPEED_BOUNDS_PRIORI_DECIDER功能简介SPEED_BOUNDS_PRIORI_DECIDER相关配置SPEED_BOUNDS_PRIORI_DECIDER流程将障碍物映射到ST图中ComputeSTBoundary(PathDecision* path_decision)ComputeSTBoundary(Obstacle* obstacle)GetOverlapBoundaryPointsComputeSTBounda…...

物理机ping不通windows server 2012

刚才尝试各种方法&#xff0c;在物理机上就是ping不能wmware中的windows server 2012 . 折腾了几个小时&#xff0c;原来是icmp 被windows server 2012 禁用了 现在使用使用以下协议就能启用Icmp协议。 netsh firewall set icmpsetting 8然后&#xff0c;就能正常ping 通虚…...

誉天HCIE-Datacom丨为什么选择誉天数通HCIE课程学习

大家好&#xff0c;我是誉天HCIE-Datacom的一名学员&#xff0c;在2022年觉得自己技术水平不够&#xff0c;想要提升自己&#xff0c;经朋友介绍在誉天报的名。 听朋友说誉天的阮Sir的课讲的非常好&#xff0c;我在B站上看了几节阮老师的课确实比之前在听得其他机构的课程讲的要…...

Python文本终端GUI框架详解

今天笔者带大家&#xff0c;梳理几个常见的基于文本终端的 UI 框架&#xff0c;一睹为快&#xff01; Curses 首先出场的是 Curses。 Curses 是一个能提供基于文本终端窗口功能的动态库&#xff0c;它可以: 使用整个屏幕 创建和管理一个窗口 使用 8 种不同的彩色 为程序提供…...

01_lwip_raw_udp_test

1.打开UDP的调试功能 &#xff08;1&#xff09;设置宏定义 &#xff08;2&#xff09;打开UDP的调试功能 &#xff08;3&#xff09;修改内容&#xff0c;串口助手打印的日志信息自动换行 2.电脑端连接 UDP发送一帧数据 3.电路板上发送一帧数据...

学习ts(十一)本地存储与发布订阅模式

localStorage实现过期时间 目录 准备 安装 npm i rollup typescript rollup-plugin-typescript2// tsconfig.json"module": "ESNext","moduleResolution": "node", "strict": false, // rollup.config.js import …...

MySQL对NULL值处理

在使用数据库时&#xff0c;有时需要表示未知值&#xff0c;这时可以使用NULL值表示。引入NULL值后&#xff0c;会对原有的使用产生影响&#xff0c;这里记录下常见的场景&#xff0c;以做记录。 NULL含义 在MySQL中&#xff0c;NULL值表示一个未知值&#xff0c;表示不可知、…...

Vector 动态数组(迭代器)

C数据结构与算法 目录 本文前驱课程 1 C自学精简教程 目录(必读) 2 Vector<T> 动态数组&#xff08;模板语法&#xff09; 本文目标 1 熟悉迭代器设计模式&#xff1b; 2 实现数组的迭代器&#xff1b; 3 基于迭代器的容器遍历&#xff1b; 迭代器语法介绍 对迭…...

多组背包恰好装满方案数

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 现在有一个大小n*1的收纳盒&#xff0c;我们手里有无数个大小为1*1和2*1的小方块&#xff0c;我们需要用这些方块填满收纳盒&#xff0c;请问我们有多少种不同的方法填满这个收纳盒 分析&…...

Oracle查询语句中做日期加减运算

在Oracle中&#xff0c;可以使用日期函数来实现日期的加减。 若想在日期上加上一定的天数&#xff0c;可以使用"INTERVAL"关键字。例如&#xff0c;如果要将一个日期加上3天&#xff0c;可以使用以下代码&#xff1a; SELECT SYSDATE INTERVAL 3 DAY FROM DUAL; …...

Unity贝塞尔曲线的落地应用-驱动飞行特效

前言 本文教你怎么用贝塞尔曲线驱动一个飞行特效 中间点的准备 开放一些可以给策划配置的变量 startPos flyEffect.transform.position; var right (GetAimPoistion(targetActor) - flyEffect.transform.position).x > 0?1:-1; midPos startPos new Vector3(righ…...

VTK——设置交互样式上的鼠标回调函数

函数介绍 VTKPointPickerInteractorStyle是一个自定义的交互样式类&#xff0c;它是VTK库中vtkInteractorStyleTrackballCamera类的子类。VTK&#xff08;Visualization Toolkit&#xff09;是一个开源的&#xff0c;跨平台的库&#xff0c;用于处理、渲染和视觉化科学数据。它…...

Flutter实现动画列表AnimateListView

由于业务需要&#xff0c;在打开列表时&#xff0c;列表项需要一个从右边飞入的动画效果&#xff0c;故封装一个专门可以执行动画的列表组件&#xff0c;可以自定义自己的动画&#xff0c;内置有水平滑动&#xff0c;缩放等简单动画。花里胡哨的动画效果由你自己来定制吧。 功…...

【LeetCode-中等题】236. 二叉树的最近公共祖先

文章目录 题目方法一&#xff1a;后序遍历 回溯 题目 方法一&#xff1a;后序遍历 回溯 解题的核心就是&#xff1a;采用后序遍历 讨论p&#xff0c;q是否在当前的root的两边&#xff0c;如在两边则返回当前节点root 如何不在两边&#xff0c;只要出现一个节点等于p或者q就…...

如何拼接两个视频在一起?

如何拼接两个视频在一起&#xff1f;在度过一个美好周末的时候&#xff0c;我和朋友一起拍摄了两组视频&#xff0c;准备将两个视频合并成一个并发布到朋友圈。这个想法非常棒&#xff0c;但是我在第一步就遇到了麻烦&#xff1a;如何将这两个视频拼接在一起&#xff1f;这听起…...

Programming abstractions in C阅读笔记:p130-p131

《Programming Abstractions In C》学习第52天&#xff0c;p130-p131&#xff0c;总结如下&#xff1a; 一、技术总结 1. pig latin game 通过pig latin game掌握字符复制&#xff0c;指针遍历等操作。 /** 输入&#xff1a;字符串&#xff0c;这里采用书中坐着自定义的get…...

如何在Windows本地快速搭建SFTP文件服务器,并通过端口映射实现公网远程访问

文章目录 1. 搭建SFTP服务器1.1 下载 freesshd服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内网连接测试成功 3 使用cpolar内网穿透3.1 创建SFTP隧道3.2 查看在线隧道列表 4. 使用SFTP客户端&#xff0…...

C#---第二十:不同类型方法的执行顺序(new / virtual / common / override)

本文介绍不同类型的方法&#xff0c;在代码中的执行顺序问题&#xff1a; 构造方法普通方法&#xff08;暂用common代替&#xff09;、虚方法&#xff08;Virtual修饰&#xff09;、New方法&#xff08;new修饰&#xff09;三个优先级相同overide方法&#xff08;会替换virtual…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...