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

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中的蜂窝材质功能可提升效率吗?

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

一句话木马攻击复现:揭示黑客入侵的实战过程

这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 准备环境 OWASP虚拟机xfp 7与xshell 7 ​ DVWA系统默认的账号密码均为&#xff1a;admin/admin 1、命令注入中复现 ​ 攻击payload 127.0.0.1 | echo "<?php eval(…...

【游戏开发教程】Unity Cinemachine快速上手,详细案例讲解(虚拟相机系统 | 新发出品 | 良心教程)

文章目录 一、前言二、插件下载三、案例1&#xff1a;第三人称自由视角&#xff0c;Free Look character场景1、场景演示2、组件参数2.1、CinemachineBrain&#xff1a;核心2.2、CinemachineFreeLook&#xff1a;第三人称自由视角相机2.2.1、设置Follow&#xff1a;跟随2.2.2、…...

当图像宽高为奇数时,如何计算 I420 格式的uv分量大小

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

结构型模式-代理模式

代理模式* 定义&#xff1a;在代理模式&#xff08;Proxy Pattern&#xff09;中&#xff0c;一个类代表另一个类的功能。这种类型的设计模式属于结构型模式。在代理模式中&#xff0c;我们创建具有现有对象的对象&#xff0c;以便向外界提供功能接口。 意图&#xff1a;为其…...

SpringBoot+Redis BitMap 实现签到与统计功能

最近项目里需要集成签到和统计功能&#xff0c;连续签到后会给用户发放一些优惠券和奖品&#xff0c;以此来吸引用户持续在该品台进行活跃。下面我们一些来聊一聊目前主流的实现方案。 因为签到和统计的功能涉及的数据量比较大&#xff0c;所以在如此大的数据下利用传统的关系…...

P5739 【深基7.例7】计算阶乘

题目描述 求 n ! n! n!&#xff0c;也就是 1 2 3 ⋯ n 1\times2\times3\dots\times n 123⋯n。 挑战&#xff1a;尝试不使用循环语句&#xff08;for、while&#xff09;完成这个任务。 输入格式 第一行输入一个正整数 n n n。 输出格式 输出一个正整数&#xff0c…...

scikit-learn中OneHotEncoder用法

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

linux操作系统的权限的深入学习(未完)

1.Linux权限的概念 Linux下有两种用户&#xff1a;超级用户&#xff08;root&#xff09;、普通用户。 超级用户&#xff1a;可以再linux系统下做任何事情&#xff0c;不受限制 普通用户&#xff1a;在linux下做有限的事情。 超级用户的命令提示符是“#”&#xff0c;普通用户…...

C 连接MySQL8

Linux 安装MySQL 8 请参考文章&#xff1a;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; //记录结…...

福利之舞:员工的心跳与企业的平衡术

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

MyBatis动态语句且如何实现模糊查询及resultType与resultMap的区别---详细介绍

前言 前面我们学习了如何使用Mybatis实现简单的增删改查。今天我们来学习如何使用动态语句来根据不同的条件生成不同的SQL语句。这在实际开发中非常有用&#xff0c;因为通常查询条件是多样化的&#xff0c;需要根据实际情况来拼接SQL语句&#xff0c;那什么是MyBatis动态语句呢…...

麒麟OS国产系统身份证阅读器web网页开发使用操作流程

1、打开麒麟软件商店&#xff0c;选择驱动&#xff0c;找到身份证阅读器&#xff0c;找到东信智能身份证社保卡读卡器&#xff0c;点击安装。 2、安装完成后&#xff0c;点击打开 3、进入读卡界面 4、进入代码集成 <script type"text/javascript">var ctnFin…...

前端面试:【事件处理】探索事件流、委托与事件对象

嗨&#xff0c;亲爱的事件探险家&#xff01;在JavaScript的世界中&#xff0c;事件处理是与用户互动的关键。本文将带你探索事件流、事件委托、常见事件类型和事件对象&#xff0c;这些知识将帮助你成为事件处理的大师。 2. 事件流&#xff1a;事件的旅程 事件流描述了事件从…...

c语言函数指针使用例子

一、是什么? c语言函数名是一段代码首地址,连接器链接时放在text段,下面例子会把函数名打印出来,.map文件内存分布查看相关代码段函数: 下面例子实现步骤: 来源于uboot 的初始化 board_f.c typedef int (*init_fun_t)(void); (1)构建gd数据类型 (2)初始化全局gd变量 (3)实…...

云计算技术应用专业实训室建设方案

一、 云计算技术应用系统概述 云计算技术是一种基于互联网的计算模式&#xff0c;通过将计算资源&#xff08;如服务器、存储、数据库、网络、软件等&#xff09;提供为一种服务&#xff0c;使用户能够按需获取和使用这些资源&#xff0c;而无需拥有和管理实际的物理设备。云计…...

C语言学习之共用体(union)的运用

C语言中的共用体&#xff1a;伪代码表示&#xff1a; union 类型名{ 数据类型1 成员1; 数据类型2 成员2; 数据类型3 成员3; . . . 数据类型n 成员n; };共用体的特点&#xff1a;1.所有的成员是共享同一块内存空间的2.所有成员的首地址是一样的&#xff1b;3.大小取决于共用体中…...

Sentinel 控制台(集群流控管理)

规则配置 要通过 Sentinel 控制台配置集群流控规则&#xff0c;需要对控制台进行改造。我们提供了相应的接口进行适配。 从 Sentinel 1.4.0 开始&#xff0c;我们抽取出了接口用于向远程配置中心推送规则以及拉取规则&#xff1a; DynamicRuleProvider<T>: 拉取规则Dy…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

微信小程序云开发平台MySQL的连接方式

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

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

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

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

MySQL体系架构解析(三):MySQL目录与启动配置全解析

MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录&#xff0c;这个目录下存放着许多可执行文件。与其他系统的可执行文件类似&#xff0c;这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中&#xff0c;用…...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上

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