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

【LeetCode】在每个树行中找最大值(DFS 深度优先搜索)

📌题目链接:LeetCode 515. 在每个树行中找最大值


题目描述

给定一棵二叉树的根节点 root,请找出该二叉树中每一层的最大值。


示例

示例 1

示例图1

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

示例 2

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

思路分析

本题需要找出每一层的最大值关键词是“每一层”,所以自然联想到可以用层数作为 key来记录。

整体思路是:

  • 使用一个哈希表HashMap<Integer, Integer>),记录每层的最大值。

    • key:层数

    • value:该层目前为止遇到的最大节点值

  • 采用**深度优先搜索(DFS)**遍历整棵树。

  • 在遍历过程中实时更新每一层的最大值。

  • 最后按照层数顺序,提取出结果。


代码实现

首先定义二叉树节点 TreeNode

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

然后是主体解法:

import java.util.*;class Solution {// 用哈希表记录每层的最大值private Map<Integer, Integer> levelMax = new HashMap<>();public List<Integer> largestValues(TreeNode root) {dfs(root, 0);List<Integer> result = new ArrayList<>();for (int i = 0; i < levelMax.size(); i++) {result.add(levelMax.get(i));}return result;}private void dfs(TreeNode node, int level) {if (node == null) return;// 更新当前层最大值levelMax.put(level, Math.max(levelMax.getOrDefault(level, Integer.MIN_VALUE), node.val));// 递归遍历左右子树dfs(node.left, level + 1);dfs(node.right, level + 1);}
}

细节讲解

  • dfs(node, level) 方法中,每递归一层,level 加 1。

  • levelMax.getOrDefault(level, Integer.MIN_VALUE):如果当前层还没有记录,默认使用最小值。

  • 最后遍历 map,按层序输出。


复杂度分析

  • 时间复杂度:O(N),其中 N 是树中的节点个数,需要遍历每个节点一次。

  • 空间复杂度:O(H),H 为树的高度,主要是递归调用栈的空间。


小贴士:为什么可以用 DFS?

虽然找层次一般第一反应是 BFS(广度优先搜索),但其实 DFS 也能做,只要我们在递归过程中维护当前层数,一样能正确处理。

当然,如果用 BFS,会更直观一些,比如用队列按层遍历,每层取最大值,也是不错的方法。


总结

✅ 本题用 DFS + 哈希表 很轻松就能解决,重点是掌握:

  • 递归时带上层数信息

  • 每层维护最大值

如果想进一步练习,可以尝试用 BFS(广度优先遍历) 来做一版!


如果这篇文章对你有帮助,别忘了点个 赞👍收藏⭐ 支持一下呀!
有任何问题也欢迎在评论区交流~

相关文章:

【LeetCode】在每个树行中找最大值(DFS 深度优先搜索)

&#x1f4cc;题目链接&#xff1a;LeetCode 515. 在每个树行中找最大值 题目描述 给定一棵二叉树的根节点 root&#xff0c;请找出该二叉树中每一层的最大值。 示例 示例 1 输入: root [1,3,2,5,3,null,9] 输出: [1,3,9]示例 2 输入: root [1,2,3] 输出: [1,3]思路分析 …...

深度学习中模型量化那些事

在深度学习中模型量化可以分为3块知识点&#xff0c;数据类型、常规模型量化与大模型量化。本文主要是对这3块知识点进行浅要的介绍。其中数据类型是模型量化的基本点。常规模型量化是指对普通小模型的量化实现&#xff0c;通常止步于int8的量化&#xff0c;绝大部分推理引擎都…...

手写JSX实现虚拟DOM

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 &#x1f35a; 蓝桥云课签约作者、…...

Redis的Spring客户端的使用

Redis 的 Spring 客户端使用 前面使用 Jedis 时, 是借助 Jedis 对象中的各种方法来对 Redis 进行操作. 而在 Spring 框架中, 则是通过 StringRedisTemplate 来操作 Redis. 最开始提供的类是 RedisTemplate, StringRedisTemplate 是 RedisTemplate 的子类, 专门用于处理文本数据…...

7.4 SVD 的几何背景

一、SVD 的几何解释 SVD 将矩阵分解成三个矩阵的乘积&#xff1a; ( 正交矩阵 ) ( 对角矩阵 ) ( 正交矩阵 ) (\pmb{正交矩阵})\times(\pmb{对角矩阵})(\pmb{正交矩阵}) (正交矩阵)(对角矩阵)(正交矩阵)&#xff0c;用几何语言表述其几何背景&#xff1a; ( 旋转 ) ( 伸缩 )…...

WEB安全--内网渗透--LMNTLM基础

一、前言 LM Hash和NTLM Hash是Windows系统中的两种加密算法&#xff0c;不过LM Hash加密算法存在缺陷&#xff0c;在Windows Vista 和 Windows Server 2008开始&#xff0c;默认情况下只存储NTLM Hash&#xff0c;LM Hash将不再存在。所以我们会着重分析NTLM Hash。 在我们内…...

BN 层做预测的时候, 方差均值怎么算

✅ 一、Batch Normalization&#xff08;BN&#xff09;回顾 BN 层在训练和推理阶段的行为是不一样的&#xff0c;核心区别就在于&#xff1a; 训练时用 mini-batch 里的均值方差&#xff0c;预测时用全局的“滑动平均”均值方差。 &#x1f9ea; 二、训练阶段&#xff08;Trai…...

【AI热点】meta新发布llama4深度洞察(快速认知)

以下是一份针对新发布的 Llama 4 模型的深度洞察报告。报告将从模型家族整体概览、技术创新与架构特点、功能与性能表现、多模态与超长上下文、与主流竞品比较、应用场景与未来展望六大部分进行分析和总结。 一、Llama 4 家族整体概览 家族成员 Llama 4 Scout 总参数量约 10…...

大厂机考——各算法与数据结构详解

目录及其索引 哈希双指针滑动窗口子串普通数组矩阵链表二叉树图论回溯二分查找栈堆贪心算法动态规划多维动态规划学科领域与联系总结​​ 哈希 ​​学科领域​​&#xff1a;计算机科学、密码学、数据结构 ​​定义​​&#xff1a;通过哈希函数将任意长度的输入映射为固定长度…...

前端面试的ACM模式笔试输入模式

在前端面试的ACM模式笔试中&#xff0c;输入参数的读取是核心技能之一&#xff0c;以下是常见场景的代码实现及注意事项&#xff1a; 一、JavaScript的两种输入模式 1. V8模式&#xff08;浏览器环境/部分OJ平台&#xff09; • 核心方法&#xff1a;通过 read_line() 或 rea…...

AIP-215 API特定proto

编号215原文链接AIP-215: API-specific protos状态批准创建日期2018-10-01更新日期2018-10-01 API通常使用API特定proto定义&#xff0c;偶尔依赖通用组件。保持API相互隔离可以避免版本问题和客户端库打包问题。 指南 所有特定于某个API的protos 必须 位于带有主版本号的包…...

计算机毕业设计指南

哈喽各位大四的小伙伴们&#xff0c;以下是一份详细的计算机专业毕业设计指南&#xff0c;涵盖选题、流程、技术选型、开发建议和常见问题解决方案&#xff0c;帮助你高效完成毕业设计&#xff0c;如有其他问题&#xff0c;欢迎点击文章末尾名片进行咨询&#xff0c;可免费赠送…...

内网渗透-Linux提权之suid提权

Linux提权之suid提权 suid简介 在Linux系统中的文件&#xff0c;通常有rwx也就是读、写、执行三种权限&#xff0c;但其实还有第四种权限&#xff0c;也就是suid权限。在执行拥有suid权限的文件的过程中&#xff0c;会获得文件属主的权限。例如&#xff0c;当cat命令具有suid…...

FreeCAD傻瓜教程-钣金工作台SheetMetal的安装和简单使用

起因&#xff1a; 因为需要在平面上固定一段比较短的铝型材&#xff0c;角码太占用横向空间&#xff0c;所以想做两个Z字固定片&#xff0c;将型材从两端进行螺丝固定。在绘图的时候想到&#xff0c;板材折弯后的长度。开孔位置等都会有所变化&#xff0c;如何确定相关的尺寸&a…...

语法: ptr=malloc(size)

MALLOC( ) 语法: ptrmalloc(size) 参数: size是一个整数,表示被分配的字节个数; 返回值: 如果允许的话,返回值是一个指向被分配存储器的指针;否则的话, 返回值是一个非指针; 功能: 该函数用来分配一定大小的空间给一个对象,其大小为size,但该空间的值为不确定值; 有…...

(五)安卓开发中的滚动布局(ScrollView / HorizontalScrollView)使用详解

在安卓开发中&#xff0c;滚动布局是一种非常重要的布局方式&#xff0c;它允许用户在屏幕上滚动查看超出屏幕范围的内容。本文将详细讲解滚动布局的基本概念、主要属性、代码示例以及具体的使用场景&#xff0c;帮助开发者深入理解并灵活运用。 基本概念 滚动布局本质上是一个…...

Matlab:三维绘图

目录 1.三维曲线绘图命令&#xff1a;plot3 实例——绘制空间直线 实例——绘制三角曲线 2.三维曲线绘图命令&#xff1a;explot3 3.三维网格命令&#xff1a;mesh 实例——绘制网格面 实例——绘制山峰曲面 实例——绘制函数曲线 1.三维曲线绘图命令&#xff1a;plot3 …...

Java中String、Array、List的相互转换工具类

Java中的数组与集合类的使用,系列文章: 《Java数组》 《Java集合类》 《Java中String、Array、List的相互转换工具类》 《Java8使用Stream流实现List列表的查询、统计、排序、分组》 《Java实现List集合的排序:Comparable接口、Comparator接口、stream().sorted()方法的使用…...

【HFP】蓝牙HFP应用层核心技术研究

免提配置文件(Hands-Free Profile, HFP)作为实现设备间音频通信的关键协议,广泛应用于车载系统、蓝牙耳机等场景。本文将基于最新技术规范,深入剖析HFP应用层的功能要求、协议映射及编解码器支持,为蓝牙开发工程师提供详尽的技术指南。 一、HFP应用层功能全景图 HFP定义…...

P1734 最大约数和(dp)

题目描述 选取和不超过 S 的若干个不同的正整数&#xff0c;使得所有数的约数&#xff08;不含它本身&#xff09;之和最大。 输入格式 输入一个正整数 S。 输出格式 输出最大的约数之和。 输入输出样例 输入 #1复制 11 输出 #1复制 9 说明/提示 【样例说明】 取数…...

P1596 [USACO10OCT] Lake Counting S(DFS)

题意翻译 由于近期的降雨&#xff0c;雨水汇集在农民约翰的田地不同的地方。我们用一个 NM(1≤N≤100,1≤M≤100) 的网格图表示。每个网格中有水&#xff08;W&#xff09; 或是旱地&#xff08;.&#xff09;。一个网格与其周围的八个网格相连&#xff0c;而一组相连的网格视…...

ROS Bag 数据裁剪教程

ROS Bag 数据裁剪教程 文章目录 ROS Bag 数据裁剪教程1. Bag 数据显示2. Bag 数据裁剪2.1 基本命令2.2 过滤更多条件2.3 注意事项 在使用 ROS 进行机器人开发和调试时&#xff0c;我们经常需要使用 rosbag 工具来记录和回放传感器数据、日志等信息。本文将介绍如何使用 rosba…...

AF3 OpenFoldDataLoader类解读

AlphaFold3 data_modules 模块的 OpenFoldDataLoader 类继承自 PyTorch 的 torch.utils.data.DataLoader。该类主要对原始 DataLoader 做了批数据增强与控制循环迭代次数(recycling)相关的处理。 源代码: class OpenFoldDataLoader(torch.utils.data.DataLoader):def __in…...

基于内容的课程推荐网站的设计与实现00(SSM+htmlL)

基于内容的课程推荐网站的设计与实现(SSMhtml) 该系统是一个基于内容的课程推荐网站&#xff0c;旨在为用户提供个性化的课程推荐。系统包含多个模块&#xff0c;如教学视频、教学案例、课程信息、系统公告、个人中心和后台管理。用户可以通过首页访问不同的课程分类&#xff…...

【Linux网络】以太网(数据链路层)

认识以太网 两台主机在同一个局域网下是可以进行通信的,因为每台主机都有自己的标识符. 太网是负责直接相连的两个设备之间的可靠数据传输,"以太网" 不是一种具体的网络, 而是一种技术标准; 既包含了数据链路层的内容, 也包含了一些物理层的内容.在局域网中&#x…...

大模型学习五:‌DeepSeek Janus-Pro-7B 多模态半精度本地部署指南:环境是腾讯cloudstudio高性能GPU 16G免费算力

一、说明介绍 由于前面玩过了&#xff0c;所以啥也别说&#xff0c;就是显存不够玩&#xff0c;要优化&#xff0c;没钱就是这么回事&#xff0c;看下图&#xff0c;显存实际只有15360M&#xff0c;确实是16G 如何获取算力 二、如何获取算力 1、进入网址 Cloud Studio 2、没有…...

Spring 中的事务

&#x1f9fe; 一、什么是事务&#xff1f; &#x1f9e0; 通俗理解&#xff1a; 事务 一组操作&#xff0c;要么全部成功&#xff0c;要么全部失败&#xff0c;不能只做一半。 比如你转账&#xff1a; A 账户扣钱B 账户加钱 如果 A 扣了钱但 B 没收到&#xff0c;那就出问…...

2025-04-06 NO.2 Quest3 基础配置与打包

文章目录 1 场景配置1.1 开启手势支持1.2 创建 OVRCameraRig1.3 创建可交互 Cube 2 打包配置 环境&#xff1a; Windows 11Unity6000.0.42f1 Quest3 开发环境配置见 2025-03-17 NO.1 Quest3 开发环境配置教程_quest3 unity 开发流程-CSDN博客。 1 场景配置 1.1 开启手势支持 …...

人脸考勤管理一体化系统(人脸识别系统,签到打卡)

人脸考勤管理一体化系统 项目介绍 本项目是基于Flask、SQLAlchemy、face_recognition库的人脸考勤管理一体化系统。 系统通过人脸识别技术实现员工考勤打卡、人脸信息采集、人脸模型训练等功能。 项目采用前后端分离的技术框架&#xff0c;基于Flask轻量级Web框架搭建后端服务…...

LeetCode 每日一题 2025/3/31-2025/4/6

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/31 2278. 字母在字符串中的百分比4/1 2140. 解决智力问题4/2 2873. 有序三元组中的最大值 I4/3 2874. 有序三元组中的最大值 II4/4 1123. 最深叶节点的最近公共祖先4/5 1…...

mybatis plus 实体类基于视图,更新单表的时候报视图或函数‘v_视图名‘不可更新,因为修改会影响多个基表的错误的简单处理方法。

1、之前的文章中写了一下基于视图的实体&#xff0c;因为当前测试通过了&#xff0c;可能有缓存。 2、然后今天又用到了这个方法&#xff0c;发现报错了&#xff1a; 建了一下视图&#xff0c;将实体类绑定到了视图中&#xff0c;并不是原表中。 3、用mybatis提供的注解或者x…...

语法: i8=make8( var, offset);

MAKE8( ) 语法: i8make8( var, offset); 参数: var是16位或32位整数; offset是字节的偏移量,为1,2或3; 返回值: 返回值是一个8位整数; 功能: 该函数用来摘取以var为基址, offset为偏移量,所指向单元的字节;除了执行单字节复制之外,还相当于i8( ( var>>(offset…...

Seata TCC模式是怎么实现的?

Seata TCC 模式实现原理 TCC(Try-Confirm-Cancel)是 Seata 提供的分布式事务解决方案之一,适用于 高并发、高性能 场景,通过 业务补偿 保证最终一致性。其核心思想是将事务拆分为三个阶段: Try:预留资源(冻结数据,检查约束)。Confirm:确认提交(真正扣减资源)。Can…...

sentinel新手入门安装和限流,热点的使用

1 sentinel入门 1.1下载sentinel控制台 &#x1f517;sentinel管理后台官方下载地址 下载完毕以后就会得到一个jar包 1.2启动sentinel 将jar包放到任意非中文目录&#xff0c;执行命令&#xff1a; java -jar 名字.jar如果要修改Sentinel的默认端口、账户、密码&#xff…...

对责任链模式的理解

对责任链模式的理解 一、场景1、题目【[来源](https://kamacoder.com/problempage.php?pid1100)】1.1 题目描述1.2 输入描述1.3 输出描述1.4 输入示例1.5 输出示例 二、不采用责任链模式1、代码2、缺点 三、采用责任链模式1、代码2、优点 四、思考 一、场景 1、题目【来源】 …...

AGI大模型(11):RAG系统

1 RAG概念 RAG(Retrieval Augmented Generation)顾名思义,通过检索外部数据,增强大模型的生成效果。 RAG即检索增强生成,为LLM提供了从某些数据源检索到的信息,并基于此修正生成的答案。RAG基本上是Search + LLM 提示,可以通过大模型回答查询,并将搜索算法所找到的信…...

请问你了解什么测试方法?

测试方法在软件测试中是保障软件质量的关键手段,我将从黑盒测试、白盒测试、灰盒测试等方面为你介绍常见的测试方法: 黑盒测试方法 黑盒测试把软件看作一个黑盒子,不考虑内部结构和实现细节,只关注输入和输出。 等价类划分法:将输入数据划分为有效等价类和无效等价类,从…...

【springcloud】快速搭建一套分布式服务springcloudalibaba(三)

第三篇 基于nacos搭建分布式项目 分布式事务&#xff08;分布式锁事务&#xff09; 项目所需 maven nacos java8 idea git mysql(下单) redis(分布式锁) 本文主要讲解客户下单时扣减库存的操作&#xff0c;网关系统/用户系统/商品系统/订单系统 请先准备好环境&#xff0…...

Nginx-keepalived-高可用

Nginx 高可用 通常 借助 Keepalived 实现&#xff0c; Keepalived 能通过 VRRP &#xff08;虚拟路由冗余协议&#xff09;让多个 Nginx 服务器 组成一个 热备集群&#xff0c;当主服务器故障时自动切换到备用服务器&#xff0c;保障服务不间断。 一、环境准备 角色IP 地址主…...

Linux系统管理(十九)——欧拉系统硬盘挂载、网络配置以及Docker环境安装

挂载硬盘 如果数据盘在安装操作系统的时候没有挂载&#xff0c;需要自己做一下硬盘的挂载 查看需要挂载硬盘的路径 fdisk -l这里的可挂载的硬盘路径为&#xff1a;/dev/sdb MBR分区方式转换成GPT MBR分区能挂载的硬盘空间有限&#xff0c;无法挂载全部硬盘空间&#xff0…...

vue记忆卡牌游戏

说明&#xff1a; 我希望用vue做一款记忆卡牌游戏 游戏规则如下&#xff1a; 游戏设置&#xff1a;使用3x4的网格&#xff0c;包含3对字母&#xff08;A,B,C,D,E,F&#xff09;。 ​随机洗牌&#xff1a;初始字母对被打乱顺序&#xff0c;生成随机布局。 ​游戏流程&#xff1a…...

LearnOpenGL-笔记-其九

今天让我们完结高级OpenGL的部分&#xff1a; Instancing 很多时候&#xff0c;在场景中包含有大量实例的时候&#xff0c;光是调用GPU的绘制函数这个过程都会带来非常大的开销&#xff0c;因此我们需要想办法在每一次调用GPU的绘制函数时尽可能多地绘制&#xff0c;这个过程就…...

开源软件与自由软件:一场理念与实践的交锋

在科技的世界里&#xff0c;“开源软件”和“自由软件”这两个词几乎无人不知。很多人或许都听说过&#xff0c;它们的代码是公开的&#xff0c;可以供所有人查看、修改和使用。然而&#xff0c;若要细究它们之间的区别&#xff0c;恐怕不少朋友会觉得云里雾里。今天&#xff0…...

关于使用HAL_ADC_Start函数时为什么要放在while里的解释

HAL_ADC_Start() 是一个用于启动 ADC&#xff08;模数转换器&#xff09;转换的函数&#xff0c;那为什么有时候我们会看到它被放在 while 循环里呢&#xff1f;其实取决于你使用的是哪种ADC采样方式&#xff0c;我们来细说&#x1f447;&#xff1a; &#x1f9e0; 一、先搞清…...

Qt 入门 2 之窗口部件 QWidget

Qt 入门2之窗口部件 QWidget Qt Creator 提供的默认基类只有QMainWindow、QWidget和QDialog 这3种&#xff0c;这3种窗体也是以后用得最多的&#xff0c;QMainWindow是带有菜单栏和工具栏的主窗口类,QDialog是各种对话框的基类,而它们全部继承自QWidget。不仅如此,其实所有的窗…...

在 Windows 上安装 WSL Ubuntu 的完整避坑指南:从报错到成功运行

问题背景​​ 最近在尝试通过 ​​Windows Subsystem for Linux (WSL)​​ 安装 Ubuntu 时&#xff0c;遇到了一系列报错。最初的步骤是直接使用 wsl --install 命令&#xff0c;但安装完成后发现系统中并未自动安装默认的 Ubuntu 发行版。随后尝试通过命令行手动选择发行版&a…...

STM32看门狗原理与应用详解:独立看门狗 vs 窗口看门狗(上) | 零基础入门STM32第九十四步

主题内容教学目的/扩展视频看门狗什么是看门狗&#xff0c;原理分析&#xff0c;启动喂狗方法&#xff0c;读标志位。熟悉在程序里用看门狗。 师从洋桃电子&#xff0c;杜洋老师 &#x1f4d1;文章目录 一、看门狗核心原理1.1 工作原理图解1.2 经典水桶比喻 二、STM32看门狗双雄…...

Hyperlane 框架路由功能详解:静态与动态路由全掌握

Hyperlane 框架路由功能详解&#xff1a;静态与动态路由全掌握 Hyperlane 框架提供了强大而灵活的路由功能&#xff0c;支持静态路由和动态路由两种模式&#xff0c;让开发者能够轻松构建各种复杂的 Web 应用。本文将详细介绍这两种路由的使用方法。 静态路由&#xff1a;简单…...

webpack js 逆向 --- 个人记录

网站 aHR0cDovL2FlcmZheWluZy5jb20v加密参数 参数加密位置 方法&#xff1a; 1. 构造自执行函数 !function(e) {// 加载器 }(// 模块1&#xff1b;// 模块2 )2. 找到js的加载器 3. 把上述代码放入第一步构造的自执行函数(完整扣取一整个加载器里的代码)&#xff0c;并用一…...

代码随想录回溯算法03

93.复原IP地址 本期本来是很有难度的&#xff0c;不过 大家做完 分割回文串 之后&#xff0c;本题就容易很多了 题目链接/文章讲解&#xff1a;代码随想录 视频讲解&#xff1a;回溯算法如何分割字符串并判断是合法IP&#xff1f;| LeetCode&#xff1a;93.复原IP地址_哔哩哔…...