每日一题: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的题目。

往下递归的同时需要维护一个当前路径上的最大值,而ans的话,看个人喜好,我是将ans同步传递下去进行更新。具体细节可以看看code。

class Solution {public int goodNodes(TreeNode root) {int ans = 0;int mmax = -100000; // 数据的最小值ans = dfs(root, mmax, ans);return ans;}public int dfs(TreeNode root, int mmax, int ans) {if (mmax <= root.val) {ans += 1; // 如果当前节点大于最小值,则+1mmax = root.val;}int left = ans, right = ans; // 初始化if (root.left != null) left = dfs(root.left, mmax, ans);if (root.right != null) right = dfs(root.right, mmax, ans);ans = left + right - ans; // 这块相当于返回了左右节点(包含了当前节点ans的所有好节点),这样会导致ans多加了一次,所以要减掉return ans;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/114303.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

群晖NAS:DSM7.1激活Advanced Media Extensions【自留记录】

群晖NAS&#xff1a;DSM7.1激活Advanced Media Extensions【自留记录】 本文仅半白群晖可用&#xff0c;不需要安装其他套件或者ssh修改什么 使用DS Video 网页播放视频时候&#xff0c;提示&#xff1a;【不支持当前所选音轨的文件格式&#xff0c; 因此无法播放视频。请尝试…

Vue-Router 一篇搞定 Vue3

前言 在 Web 前端开发中&#xff0c;路由是非常重要的一环&#xff0c;但是路由到底是什么呢&#xff1f; 从路由的用途上讲 路由是指随着浏览器地址栏的变化&#xff0c;展示给用户不同的页面。 从路由的实现原理上讲 路由是URL到函数的映射。它将 URL 和应用程序的不同部分…

Leetcode415 字符串相加

思路&#xff1a; 从末尾开始相加&#xff0c;进位可以最后统一处理&#xff0c;因为再怎么进也是最多只进一位 class Solution:def addStrings(self, num1: str, num2: str) -> str:# 确保1里是更长的字符串if len(num1) < len(num2):num1_list list(num2)num2_list …

解决Spring Data JPA中的NullPointerException问题

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

简单了解OSI网络模型

目录 一、协议是什么&#xff1f; 二、OSI七层模型 三、TCP/IP五层模型 一、协议是什么&#xff1f; 协议顾名思义就是通过大家伙一起协商讨论达成的统一规则和标准。网络协议就是规定用户数据信息如何在网络上传播以及实现某种网络技术所要遵循的统一标准和规则。 二、OSI…

电脑使用快捷键的各种方法

电脑使用快捷键可以帮助我们提高日常操作效率&#xff0c;例如&#xff1a; CTRLC&#xff1a;复制选中内容。 CTRLV&#xff1a;粘贴复制的内容。 CTRLX&#xff1a;剪切选中内容。 CTRLA&#xff1a;全选当前页面内容。 SHIFTDELETE&#xff1a;永久删除选中内容。 CTRL…

华为OD机试 - 租车骑绿道 - 双指针(Java 2023 B卷 100分)

目录 一、题目描述二、输入描述三、输出描述四、解题思路1、输入2、输出3、说明4、双指针算法 五、Java算法源码六、效果展示 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 一、题目描述 部门组织绿岛骑行团建活动&#xff0c;租用公共双人自行车骑行&#xff0c;…

linux————pxe网络批量装机

目录 一、概述 什么是pxe pxe组件 二、搭建交互式pxe装机 一、配置基础环境 二、配置vsftpd 三、配置tftp 四、准备pxelinx.0文件、引导文件、内核文件 一、准备pxelinux.0 二、准备引导文件、内核文件 五、配置dhcp 一、安装dhcp 二、配置dhcp 六、创建default文…

大数据精准营销怎么满足用户的个性化需求?

近年来在AI和媒体的带动下&#xff0c;大数据分析不断介入&#xff0c;各行各业都开始陆续依仗大数据营销这棵大树&#xff0c;以此来更加高效、便捷、智能、精准的服务于用户。 这就像追求恋人一样&#xff0c;投其所好方能成为眷属。 大数据精准营销的好处&#xff1a; 相…

【狂神】Spring5笔记(1-9)

目录 首页&#xff1a; 1.Spring 1.1 简介 1.2 优点 2.IOC理论推导 3.IOC本质 4.HelloSpring ERROR 5.IOC创建对象方式 5.1、无参构造 这个是默认的 5.2、有参构造 6.Spring配置说明 6.1、别名 6.2、Bean的配置 6.3、import 7.DL依赖注入环境 7.1 构造器注入 …

苹果为 Vision Pro 头显申请游戏手柄专利

苹果Vision Pro 推出后&#xff0c;美国专利局公布了两项苹果公司申请的游戏手柄专利&#xff0c;其中一项的专利图如下图所示。据 PatentlyApple 报道&#xff0c;虽然申请专利并不能保证苹果公司会推出游戏手柄&#xff0c;但是苹果公司同时也为游戏手柄申请了商标&#xff0…

【2023研电赛】安谋科技企业命题三等奖作品: 短临天气预报AI云图分析系统

本文为2023年第十八届中国研究生电子设计竞赛安谋科技企业命题三等奖分享&#xff0c;参加极术社区的【有奖活动】分享2023研电赛作品扩大影响力&#xff0c;更有丰富电子礼品等你来领&#xff01;&#xff0c;分享2023研电赛作品扩大影响力&#xff0c;更有丰富电子礼品等你来…

树的介绍(C语言版)

前言 在数据结构中树是一种很重要的数据结构&#xff0c;很多其他的数据结构和算法都是通过树衍生出来的&#xff0c;比如&#xff1a;堆&#xff0c;AVL树&#xff0c;红黑色等本质上都是一棵树&#xff0c;他们只是树的一种特殊结构&#xff0c;还有其他比如linux系统的文件系…

任意文件读取

文章目录 渗透测试漏洞原理任意文件读取1. 任意文件读取概述1.1 漏洞成因1.2 漏洞危害1.3 漏洞分类1.4 任意文件读取1.4.1 文件读取1.4.2 任意文件读取1.4.3 权限问题 1.5 任意文件下载1.5.1 一般情况1.5.2 PHP实现1.5.3 任意文件下载 2. 任意文件读取攻防2.1 路径过滤2.1.1 过…

云计算的三个主要服务模型:IaaS、PaaS 和 SaaS

文章目录 介绍基础设施即服务&#xff08;Infrastructure as a Service&#xff0c;IaaS&#xff09;平台即服务&#xff08;Platform as a Service&#xff0c;PaaS&#xff09;软件即服务&#xff08;Software as a Service&#xff0c;SaaS&#xff09; 区别基础设施即服务&…

Ansible学习笔记6

stat模块&#xff1a;获取文件的状态信息&#xff0c;类似Linux的stat状态。 获取/etc/fstab文件的状态。 [rootlocalhost tmp]# ansible group1 -m stat -a "path/etc/fstab" 192.168.17.106 | SUCCESS > {"ansible_facts": {"discovered_inter…

python基础爬虫反爬破解

文章目录 爬虫初识1. HTTP协议与WEB开发&#xff08;1&#xff09;简介&#xff08;2&#xff09;socket套接字&#xff08;3&#xff09;请求协议与响应协议 2. requests&反爬破解&#xff08;1&#xff09;UA反爬&#xff08;2&#xff09;referer反爬&#xff08;3&…

并发编程的故事——共享模型之内存

共享模型之内存 文章目录 共享模型之内存一、JVM内存抽象模型二、可见性三、指令重排序 一、JVM内存抽象模型 主要就是把cpu下面的缓存、内存、磁盘等抽象成主存和工作内存 体现在 可见性 原子性 有序性 二、可见性 出现的问题 t线程如果频繁读取一个静态变量&#xff0c;那…

高精度地图定位在高速公路自动驾驶系统中的应用

近年来随着汽车保有量不断增加&#xff0c;随之而来的是: ( 1) 严重的交通拥堵&#xff0c;通行效率低下&#xff0c;用在通行上的时间不断增加; ( 2) 交通事故频发&#xff0c;交通事故导致的伤亡人数和费用不断增加&#xff0c;而且绝大多数事故是由人为因素导致的; ( 3) 大气…

算法——排序

排序 下面的代码会用到宏定义&#xff0c;因为再C中没有swap交换函数&#xff0c;所以对于swap的宏定义代码如下&#xff1a; #define swap(a, b) {\__typeof(a) __a a; a b; b __a;\ } 稳定排序&#xff1a; 1.插入排序&#xff1a; 插入排序会将数组&#xff0c;分位两个部…