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

剑指Offer || 044.在每个树行中找最大值

题目

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

示例1:

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:1/ \3   2/ \   \  5   3   9 

示例2:

输入: root = [1,2,3]
输出: [1,3]
解释:1/ \2   3

示例3:

输入: root = [1]
输出: [1]

示例4:

输入: root = [1,null,2]
输出: [1,2]
解释:      1 \2     

示例5:

输入: root = []
输出: []

提示:

  • 二叉树的节点个数的范围是 [0,104]
  • -231 <= Node.val <= 231 - 1

注意:本题与主站 515 题相同: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

LCR 044. 在每个树行中找最大值 - 力扣(LeetCode)

题解

思路一:DFS,用先序遍历深搜,并用 curHeight来标记遍历到的当前节点的高度。当遍历到 时判断是否更新该层节点的最大值。

代码:

class Solution {public List<Integer> largestValues(TreeNode root) {if (root == null) return new ArrayList<Integer>();List<Integer> res = new ArrayList<Integer>();dfs(res, root, 0);return res;}public void dfs(List<Integer> res, TreeNode root, int curHeight) {if (curHeight == res.size()) //到新的一层,加进来第一个值res.add(root.val);else res.set(curHeight, Math.max(res.get(curHeight), root.val));if (root.left != null) dfs(res, root.left, curHeight + 1);if (root.right != null) dfs(res, root.right, curHeight + 1);}
}

思路二:BFS,层序遍历,一层一层扩展,用 maxVal来标记该层节点的最大值。当前层处理完成之后,maxVal即为当前层的最大值。

代码:

class Solution {public List<Integer> largestValues(TreeNode root) {if (root == null) return new ArrayList<Integer>();List<Integer> res = new ArrayList<Integer>();Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {int len = queue.size();//当前len确保了len--到0时,刚好处理完当前层int maxVal = Integer.MIN_VALUE;while (len > 0) {TreeNode t = queue.poll();len--;maxVal = Math.max(maxVal, t.val);if (t.left != null) queue.offer(t.left);if (t.right != null) queue.offer(t.right);}res.add(maxVal);}return res;}
}

tips:关于值传递和引用传递。在Java中用的是值传递。在其它方法里面改变引用类型的值都是通过引用改变的,当传递引用对象的时候,传递的是复制的引用的对象句柄,是复制过的,也就是在内存中复制了一个句柄,这两个句柄指向同一个对象,所以改变这个句柄对应的空间的数据会影响到外部的变量虽然是复制的,但是指向的是同一个地址,当你把这个句柄指向其它对象的引用时并不会改变原来的值(例如String),因为用的是复制过的句柄。

相关文章:

剑指Offer || 044.在每个树行中找最大值

题目 给定一棵二叉树的根节点 root &#xff0c;请找出该二叉树中每一层的最大值。 示例1&#xff1a; 输入: root [1,3,2,5,3,null,9] 输出: [1,3,9] 解释:1/ \3 2/ \ \ 5 3 9 示例2&#xff1a; 输入: root [1,2,3] 输出: [1,3] 解释:1/ \2 3示例3&#xff…...

ESP32网络开发实例-UDP数据发送与接收

UDP数据发送与接收 文章目录 UDP数据发送与接收1、UDP简单介绍2、软件准备3、硬件准备4、代码实现本文将详细介绍在Arduino开发环境中,如何实现ESP32通过UDP协议进行数据发送与接收。 1、UDP简单介绍 用户数据报协议 (UDP) 是一种跨互联网使用的通信协议,用于对时间敏感的传…...

液压自动化成套设备比例阀放大器

液压电气成套设备的比例阀放大器是一种电子控制设备&#xff0c;用于控制液压动力系统中的液压比例阀1。 比例阀放大器通常采用电子信号进行控制&#xff0c;以控制比例阀的开度和流量&#xff0c;以实现液压系统的可靠控制。比例阀放大器主要由以下组成部分&#xff1a; 驱动…...

专业144,总分440+,上岸西北工业大学827西工大信号与系统考研经验分享

我的初试备考从4月末&#xff0c;持续到初试前&#xff0c;这中间没有中断。 总的时间分配上&#xff0c;是数学>专业课>英语>政治&#xff0c;虽然大家可支配时间和基础千差万别&#xff0c;但是这么分配是没错的。 数学 时间安排&#xff1a;3月-7月&#xff1a;…...

JQuery - template.js 完美解决动态展示轮播图,轮播图不显示问题

介绍 在JQuery中,使用template.js把轮播图的图片渲染到页面后,发现无法显示。 解决方案 首先,打开控制台发现,图片dom是生成了的,排除dom的缺失其次,换了一个插件Swiper,发现效果一样,排除插件的沦丧把动态数据换成假数据,...

CC2540和CC2541的区别简单解析

CC2541理论上是CC2540的精简版&#xff0c;去除了USB接口&#xff0c;增加了1个HW1C接口。 CC2540集成了2.4GHz射频收发器&#xff0c;是一款完全兼容8051内核的无线射频单片机&#xff0c;它与蓝牙低功耗协议栈共同构成高性价比、低功耗的片上系统&#xff08;SOC&#xff09…...

Java8 新特性之Stream(八)-- Stream的collect()与Collectors的联合运用

目录 1. collect()的 收集 作用 2. collect()的 统计 作用 3. collect()的 分组 作用 4. collect()的 拼接 作用...

SpringBoot基础详解

目录 SpringBoot自动配置 基于条件的自动配置 调整自动配置的顺序 纷杂的SpringBoot Starter 手写简单spring-boot-starter示例 SpringBoot自动配置 用一句话说自动配置&#xff1a;EnableAutoConfiguration借助SpringFactoriesLoader将标准了Configuration的JavaConfig类…...

学会Docker之---应用场景和基本操作

实体机、VM和容器 实体机&#xff08;Physical Machine&#xff09;是指实际的物理设备&#xff0c;例如我们常见的计算机主机、服务器等。它们是由硬件组成&#xff0c;可以直接运行操作系统和应用程序。 虚拟机&#xff08;Virtual Machine&#xff09;是在一台物理机上通过…...

C++_linux下_非阻塞键盘控制_程序暂停和继续

1. 功能 在程序执行过程中,点击键盘p按键(pause), 程序暂停, 点击键盘上的n按键(next),程序继续执行 2. 代码 #include <iostream> #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <sys/ioctl.h> char get_keyboar…...

SQL AND, OR and NOT(与,或不是运算符)

SQL AND & OR 运算符 AND&OR运算符用于根据一个以上的条件过滤记录&#xff0c;即用于组合多个条件以缩小SQL语句中的数据。 WHERE子句可以与AND&#xff0c;OR和NOT运算符结合使用。 AND和OR运算符用于根据多个条件筛选记录&#xff1a; 如果由AND分隔的所有条件为TR…...

Python网络编程之Socket(套接字)

文章目录 一、Socket概念二、套接字的发展史及分类三、Socket的使用语法格式(基于TCP协议)1.基于TCP协议的套接字(socket)编程半连接池 2.基于UDP协议的套接字(socket)编程也可以使用服务端只接收客户端消息 黏包现象 一、Socket概念 Socket套接字&#xff0c;一种独立于协议的…...

金山终端安全系统V9.0 SQL注入漏洞复现

0x01 产品简介 金山终端安全系统是一款为企业提供终端防护的安全产品&#xff0c;针对恶意软件、病毒和外部攻击提供防范措施&#xff0c;帮助维护企业数据和网络。 0x02 漏洞概述 金山终端安全系统V9.0 /inter/update_software_info_v2.php页面存在sql注入漏洞&#xff0c;该…...

Radius OTP完成堡垒机登录认证 安当加密

Radius OTP&#xff08;One-Time Password&#xff09;是一种用于身份验证的协议&#xff0c;它通过向用户发送一个一次性密码来验证用户的身份。使用Radius OTP可以实现堡垒机登录&#xff0c;以下是一些实现步骤&#xff1a; 1、安装Radius服务器 首先需要安装Radius服务器…...

ROS opencv 人脸识别

人脸识别需要在输入的图像中确定人脸&#xff08;如果存在&#xff09;的位置、大小和姿态&#xff0c;往往用于生物特征识别、视频监听、人机交互等应用中。2001年&#xff0c;Viola和Jones提出了基于Haar特征的级联分类器对象检测算法&#xff0c;并在2002年由Lienhart和Mayd…...

文心一言 4.0 ERNIE-Bot 4.0 :ERNIE-Bot 4.0 大模型深度测试体验报告

本心、输入输出、结果 文章目录 文心一言 4.0 ERNIE-Bot 4.0 &#xff1a;ERNIE-Bot 4.0 大模型深度测试体验报告前言相关跳转文心一言 4.0 ERNIE-Bot 4.0 接口简介Bash 请求示例代码Windows 模式使用 Python 请求如果直接使用官方提供的代码文心一言 4.0 ERNIE-Bot 4.0 API 在…...

华为OD机考B卷 | 100分】阿里巴巴找黄金宝箱(JAVA题解——也许是全网最详)

前言 本人是算法小白&#xff0c;甚至也没有做过Leetcode。所以&#xff0c;我相信【同为菜鸡的我更能理解作为菜鸡的你们的痛点】。 题干 1. 题目描述 一贫如洗的樵夫阿里巴巴在去砍柴的路上&#xff0c;无意中发现了强盗集团的藏宝地&#xff0c;藏宝地有编号从0~N的箱子&…...

请求转发和重定向区别

两者区别&#xff1a; 1.转发在一次请求中完成&#xff0c;重定向是两次请求 2.转发操作发生在服务器内部&#xff0c;重定向是在浏览器执行操作 3.转发地址栏不变&#xff0c;重定向地址栏变化&#xff08;两次请求&#xff0c;两个地址&#xff09; 4.转发可以在一次请求中共…...

JS如何判断对象为空?以及各自的缺点。

JS如何判断对象为空&#xff1f;以及各自的缺点。 Object.keys() 通过 Object.keys() 来获取对象的键进行判断。 function isEmpty(obj) {return Object.keys(obj).length 0; }console.log(isEmpty({})); // true console.log(isEmpty({ a: 1 })); // false缺点&#xff1a…...

同城代驾开源版小程序开发

同城代驾开源版小程序开发 功能特性描述&#xff1a; 定价模式&#xff1a;本系统支持灵活的计价模式&#xff0c;包括白天和夜晚的起步价、起步里程、每公里价以及超时费用&#xff0c;从而满足不同时段的定价需求。 实时路径计算&#xff1a;通过集成腾讯地图的软件开发工…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...