【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] 。

解答

源代码

/*** Definition for a binary tree node.* public 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;*     }* }*/
class Solution {public int goodNodes(TreeNode root) {return dfs(root, Integer.MIN_VALUE);}public int dfs(TreeNode root, int max) {if (root == null) {return 0;}if (max > root.val) {return dfs(root.left, max) + dfs(root.right, max);}return dfs(root.left, root.val) + dfs(root.right, root.val) + 1;}
}

总结

深度遍历的时候记录前面最大的节点值,和当前节点进行比较。我蠢的……一开始把前面所有节点值全给记录下来了然后一个个对比。

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

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

相关文章

【MOS管的作用和工作原理】

数电/模电知识学习与分享001 MOS管的作用和工作原理1、MOS管基本概念2、MOS管基本原理3、MOS管广泛作用4、MOS管特点4、参考文献 MOS管的作用和工作原理 1、MOS管基本概念 MOS管(Metal-Oxide-Semiconductor Field-Effect Transistor)是一种常用的半导体…

python AI绘图教程

前提 1.安装python 2.安装git 步骤 下载stable-diffusion-webui项目(链接:GitHub - AUTOMATIC1111/stable-diffusion-webui: Stable Diffusion web UI) git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui.git 安装st…

【Go Web 篇】Go 语言进行 Web 开发:构建高性能网络应用

随着互联网的快速发展,Web 开发已经成为了软件开发领域中不可或缺的一部分。随之而来的是对于更高性能、更高效的网络应用的需求。在这个领域,Go 语言因其并发性能、简洁的语法以及丰富的标准库而备受关注。本篇博客将深入探讨如何使用 Go 语言进行 Web …

centos7设置静态IP地址

安装完成系统后,接下来就是配置静态IP地址,如下: 进入编辑模式vim /etc/sysconfig/network-scripts/ifcfg-ens33 文件名不一定是ifcfg-ens33,到/etc/sysconfig/network-scripts下面找下是哪个文件 修改 : BOOTPROTO…

Python OCR 使用easyocr库将图片中的文章提取出来

Python OCR 使用easyocr库将图片中的文章提取出来 初环境内容步骤一:安装easyocr库步骤二:导入必要的库步骤三:创建OCR阅读器对象步骤四:指定要识别的图片路径步骤五:执行OCR识别并提取文章内容步骤六:遍历…

深入分析负载均衡情景

本文出现的内核代码来自Linux5.4.28,为了减少篇幅,我们尽量不引用代码,如果有兴趣,读者可以配合代码阅读本文。 一、有几种负载均衡的方式? 整个Linux的负载均衡器有下面的几个类型: 实际上内核的负载均衡…

【TI毫米波雷达笔记】UART串口外设配置及驱动(以IWR6843AOP为例)

【TI毫米波雷达笔记】UART串口外设初始化配置及驱动(以IWR6843AOP为例) 最基本的工程建立好以后 需要给SOC进行初始化配置 int main (void) {//刷一下内存memset ((void *)L3_RAM_Buf, 0, sizeof(L3_RAM_Buf));int32_t errCode; //存放SOC初…

同态比较算法

参考文献: [PS73] Paterson M S, Stockmeyer L J. On the number of nonscalar multiplications necessary to evaluate polynomials[J]. SIAM Journal on Computing, 1973, 2(1): 60-66.[IZ21] Iliashenko I, Zucca V. Faster homomorphic comparison operations …

redis7高级篇3 数据量亿级别的统计分析(hyperloglog,bitmap,geo)

一 亿级别统计分类 1.1 统计分类 1.聚合统计:统计多个集合聚合的结果,也就是多个集合之间交并差的统计。 2.排序统计:在需要展示最新列表,排行榜等场景时,如果数据更新频繁或者需要分页时,建议使用zset12…

滚珠螺杆导程对精度有影响吗?

滚珠螺杆的导程也称螺距,即螺杆每旋转一周螺母直线运动的距离,导程与直线速度有关,在输入转速一定的情况下,导程越大速度越快。正常来说,选择导程时,尽量选5和10最好。 很多人一直觉得导程会影响滚珠螺杆的…

【安卓】自定义View实现画板涂鸦等功能

一、实现效果 二、代码 1、MainActivity.class package com.lsl.mydrawingboarddemo;import androidx.appcompat.app.AppCompatActivity; import androidx.core.content.ContextCompat;import android.os.Bundle; import android.os.Handler; import android.view.View; impo…

73 # 发布自己的 http-server 到 npm

1、添加 .npmignore 文件,忽略不需要的文件 public2、去官网https://www.npmjs.com/检查自己的包名是否被占用 3、切换到官方源,然后检查确认 nrm use npm nrm ls4、登录 npm 账号 npm login5、发布 npm publish6、查看发布情况,发布成功…

npm 卸载 vuecli后还是存在

运行了npm uninstall vue-cli -g,之后是up to date in,然后vue -V,版本号一直都在,说明没有卸载掉 1、执行全局卸载命令 npm uninstall vue-cli -g 2、删除vue原始文件 查看文件位置,找到文件删掉 where vue 3、再…

山西电力市场日前价格预测【2023-08-27】

日前价格预测 预测明日(2023-08-27)山西电力市场全天平均日前电价为318.11元/MWh。其中,最高日前电价为356.66元/MWh,预计出现在19: 15。最低日前电价为273.48元/MWh,预计出现在04: 30。 价差方向预测 1: 实…

Jenkins的定时任务配置

jenkins配置定时任务位置(点击日程表的问好可查看语法配置) jenkins的定时任务的参数 # 定时任务参数(每个参数之间使用tab键或空格分隔)MINUTE HOUR DOM MONTH DOW 参数解释取值范围 MINUTE 分钟0-59HOUR小时0-23DOM一月的天数1-31MONTH月份1-12DOW 一周的天数0…

实验七 Linux 内核移植

【实验目的】 掌握 Linux 内核配置和编译的基本方法 【实验环境】 ubuntu 14.04 发行版FS4412 实验平台交叉编译工具:arm-none-linux-gnueabi- 【注意事项】 实验步骤中以“$”开头的命令表示在 ubuntu 环境下执行,以“#”开头的命令表 示在开发板下…

PHP 安装Composer,vue前端依赖包

电脑安装Composer 官网下载:https://getcomposer.org/Composer-Setup.exe 后端安装: 检查是否安装依赖: 安装Composer install 或 Composer i 前端安装: yarn install 安装依赖

vr内容编辑软件降低了虚拟现实项目开发门槛

VR虚拟场景编辑器是一种专门用于创建、修改和设计虚拟场景的工具。它利用vr虚拟现实技术,让用户可以在三维空间中直接对场景进行操作和编辑。这种编辑器的出现,使得用户可以更加直观、自由地进行场景设计和制作,为诸多领域带来了新的可能性。…

Linux(基础篇一)

Linux基础篇 Linux基础篇一1. Linux文件系统与目录结构1.1 Linux文件系统1.2 Linux目录结构 2. VI/VIM编辑器2.1 vi/vim是什么2.2 模式间的转换2.3 一般模式2.4 插入模式2.4.1 进入编辑模式2.4.2 退出编辑模式 2.5 命令模式 3. 网络配置3.1 网络连接模式3.2 修改静态ip3.3 配置…

AI夏令营第三期用户新增挑战赛学习笔记

1、数据可视化 1.数据探索和理解:数据可视化可以帮助我们更好地理解数据集的特征、分布和关系。通过可视化数据,我们可以发现数据中的模式、异常值、缺失值等信息,从而更好地了解数据的特点和结构。2.特征工程:数据可视化可以帮助…
推荐文章