Leetcode每日一题:1448. 统计二叉树中好节点的数目
原题
给你一棵根为 root
的二叉树,请你返回二叉树中好节点的数目。
「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。
示例 1:
输入:root = [3,1,4,3,null,1,5] 输出:4 解释:图中蓝色节点为好节点。 根节点 (3) 永远是个好节点。 节点 4 -> (3,4) 是路径中的最大值。 节点 5 -> (3,4,5) 是路径中的最大值。 节点 3 -> (3,1,3) 是路径中的最大值。
示例 2:
输入:root = [3,3,null,4,2] 输出:3 解释:节点 2 -> (3, 3, 2) 不是好节点,因为 "3" 比它大。
示例 3:
输入:root = [1] 输出:1 解释:根节点是好节点。
提示:
- 二叉树中节点数目范围是
[1, 10^5]
。 - 每个节点权值的范围是
[-10^4, 10^4]
。
解题思路
显然我们需要遍历每个节点,并且将当前路径上最大值一起往下传,是一个和路径深度有关系的问题,考虑使用DFS实现遍历:
class Solution {
public:int goodNodes(TreeNode* root) {return dfs(root);}void dfs(TreeNode* root) {if(root == nullptr){return;}visit(root);dfs(root->left);dfs(root->right);}
};
假设我们当前有一个节点root和路径上传下来的最大值path_max。如果当前节点值小于path_max,那我们继续把path_max传给它的左右节点。如果当前节点值大于path_max,则把path_max设为当前节点值,并且把path_max传给它的左右节点。而当前节点的好节点数,等于左右节点的号节点数之和,加上1,如果当前节点是好节点,否则不加。考虑到根节点一定是好节点,我们可以用INT_MIN作为path_max的初始值。于是我们得到完整的实现:
class Solution {
public:int goodNodes(TreeNode* root) {return dfs(root,INT_MIN);}void dfs(TreeNode* root, int path_max) {if(root == nullptr){return 0;}int res = 0;if(root->val >= path_max){res++;path_max = root->val;}res += dfs(root->left, path_max);res += dfs(root->right, path_max);return res;}
};
相关文章:

Leetcode每日一题:1448. 统计二叉树中好节点的数目
原题 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 输入:root [3,1,4,3,null,1,5] 输出:4 解…...

华为OD七日集训第2期 - 按算法分类,由易到难,循序渐进,玩转OD(文末送书)
目录 一、适合人群二、本期训练时间三、如何参加四、7日集训第2期五、精心挑选21道高频100分经典题目,作为入门。第1天、逻辑分析第2天、字符串处理第3天、数据结构第4天、递归回溯第5天、二分查找第6天、深度优先搜索dfs算法第7天、动态规划 六、集训总结1、《代码…...

3d max插件CG MAGIC中的蜂窝材质功能可提升效率吗?
工作中能提升效率也都是大家所想的,对于设计师的一个设计过程中,可能想怎么样可以更快呀,是哪个步骤慢了呢? 这样的结果只能说会很多,但是建模这个步骤,肯定是有多无少的。 为了让模型更加逼真,…...

一句话木马攻击复现:揭示黑客入侵的实战过程
这篇文章旨在用于网络安全学习,请勿进行任何非法行为,否则后果自负。 准备环境 OWASP虚拟机xfp 7与xshell 7 DVWA系统默认的账号密码均为:admin/admin 1、命令注入中复现 攻击payload 127.0.0.1 | echo "<?php eval(…...

【游戏开发教程】Unity Cinemachine快速上手,详细案例讲解(虚拟相机系统 | 新发出品 | 良心教程)
文章目录 一、前言二、插件下载三、案例1:第三人称自由视角,Free Look character场景1、场景演示2、组件参数2.1、CinemachineBrain:核心2.2、CinemachineFreeLook:第三人称自由视角相机2.2.1、设置Follow:跟随2.2.2、…...

当图像宽高为奇数时,如何计算 I420 格式的uv分量大小
背景 I420 中 yuv 数据存放在3个 planes 中。 网上一般说 I420 数据大小为 widthheight1.5 但是当 width 和 height 是奇数时,这个计算公式会有问题。 I420 中 u 和 v 的宽高分别为 y 的一半。 但是当不能整除时,是如何取整呢?向上还是向下&…...

结构型模式-代理模式
代理模式* 定义:在代理模式(Proxy Pattern)中,一个类代表另一个类的功能。这种类型的设计模式属于结构型模式。在代理模式中,我们创建具有现有对象的对象,以便向外界提供功能接口。 意图:为其…...
SpringBoot+Redis BitMap 实现签到与统计功能
最近项目里需要集成签到和统计功能,连续签到后会给用户发放一些优惠券和奖品,以此来吸引用户持续在该品台进行活跃。下面我们一些来聊一聊目前主流的实现方案。 因为签到和统计的功能涉及的数据量比较大,所以在如此大的数据下利用传统的关系…...
P5739 【深基7.例7】计算阶乘
题目描述 求 n ! n! n!,也就是 1 2 3 ⋯ n 1\times2\times3\dots\times n 123⋯n。 挑战:尝试不使用循环语句(for、while)完成这个任务。 输入格式 第一行输入一个正整数 n n n。 输出格式 输出一个正整数,…...

scikit-learn中OneHotEncoder用法
One-Hot编码,又称为一位有效编码,是分类变量作为二进制向量的表示。这首先要求将分类值映射到整数值,然后,每个整数值被表示为二进制向量,将整数索引标记为1,其余都标为0。 OneHotEncoder()常用参数解释 …...

linux操作系统的权限的深入学习(未完)
1.Linux权限的概念 Linux下有两种用户:超级用户(root)、普通用户。 超级用户:可以再linux系统下做任何事情,不受限制 普通用户:在linux下做有限的事情。 超级用户的命令提示符是“#”,普通用户…...

C 连接MySQL8
Linux 安装MySQL 8 请参考文章:Docker 安装MySQL 8 详解 Visual Studio 2022 编写C 连接MySQL 8 C源码 #include <stdio.h> #include <mysql.h> int main(void) {MYSQL mysql; //数据库句柄MYSQL_RES* res; //查询结果集MYSQL_ROW row; //记录结…...

福利之舞:员工的心跳与企业的平衡术
引言:员工福利与满意度的关系 在现代企业中,员工福利已经不仅仅是一种待遇,而是与员工满意度、忠诚度和生产力紧密相连的关键因素。一个合理且吸引人的福利制度可以大大提高员工的工作积极性,同时也能够吸引和留住顶尖的人才。但…...

MyBatis动态语句且如何实现模糊查询及resultType与resultMap的区别---详细介绍
前言 前面我们学习了如何使用Mybatis实现简单的增删改查。今天我们来学习如何使用动态语句来根据不同的条件生成不同的SQL语句。这在实际开发中非常有用,因为通常查询条件是多样化的,需要根据实际情况来拼接SQL语句,那什么是MyBatis动态语句呢…...

麒麟OS国产系统身份证阅读器web网页开发使用操作流程
1、打开麒麟软件商店,选择驱动,找到身份证阅读器,找到东信智能身份证社保卡读卡器,点击安装。 2、安装完成后,点击打开 3、进入读卡界面 4、进入代码集成 <script type"text/javascript">var ctnFin…...
前端面试:【事件处理】探索事件流、委托与事件对象
嗨,亲爱的事件探险家!在JavaScript的世界中,事件处理是与用户互动的关键。本文将带你探索事件流、事件委托、常见事件类型和事件对象,这些知识将帮助你成为事件处理的大师。 2. 事件流:事件的旅程 事件流描述了事件从…...
c语言函数指针使用例子
一、是什么? c语言函数名是一段代码首地址,连接器链接时放在text段,下面例子会把函数名打印出来,.map文件内存分布查看相关代码段函数: 下面例子实现步骤: 来源于uboot 的初始化 board_f.c typedef int (*init_fun_t)(void); (1)构建gd数据类型 (2)初始化全局gd变量 (3)实…...

云计算技术应用专业实训室建设方案
一、 云计算技术应用系统概述 云计算技术是一种基于互联网的计算模式,通过将计算资源(如服务器、存储、数据库、网络、软件等)提供为一种服务,使用户能够按需获取和使用这些资源,而无需拥有和管理实际的物理设备。云计…...
C语言学习之共用体(union)的运用
C语言中的共用体:伪代码表示: union 类型名{ 数据类型1 成员1; 数据类型2 成员2; 数据类型3 成员3; . . . 数据类型n 成员n; };共用体的特点:1.所有的成员是共享同一块内存空间的2.所有成员的首地址是一样的;3.大小取决于共用体中…...

Sentinel 控制台(集群流控管理)
规则配置 要通过 Sentinel 控制台配置集群流控规则,需要对控制台进行改造。我们提供了相应的接口进行适配。 从 Sentinel 1.4.0 开始,我们抽取出了接口用于向远程配置中心推送规则以及拉取规则: DynamicRuleProvider<T>: 拉取规则Dy…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...