当前位置: 首页 > 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…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...