首页 > 其他分享 >力扣---1448. 统计二叉树中好节点的数目

力扣---1448. 统计二叉树中好节点的数目

时间:2023-05-15 20:47:52浏览次数:45  
标签:力扣 return max dfs --- 二叉树 root 节点

给你一棵根为 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] 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/count-good-nodes-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


 

当前节点子树的好节点数等于左子树的好节点数加右子树的好节点数。

而当当前节点的数值大于路径上最大的值时,该节点为好节点。

可以想到利用递归,从叶节点开始数好节点的个数,这样可以避免重复计算。

class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }
    private int dfs(TreeNode root, int max) {
        if (root == null) {
            return 0;
        }
        if (root.val >= max) {
            max = root.val;
            // 当前节点是好节点时
            return dfs(root.left, max) + dfs(root.right, max) + 1;
        } else {
            return dfs(root.left, max) + dfs(root.right, max);
        }
    }
}

 

标签:力扣,return,max,dfs,---,二叉树,root,节点
From: https://www.cnblogs.com/allWu/p/17403027.html

相关文章

  • htmlParser源码分析之1---类图
         需要做一个垂直搜索引擎,比较了nekohtml和htmlparser的功能,尽管nekohtml在容错性、性能等方面的口碑好像比htmlparser好(htmlunit也用的是nekohtml),但感觉nekohtml的测试用例和文档都比htmlparser都少,而且htmlparser基本上能够满足垂直搜索引擎页面处理分析的需......
  • Java设计模式-简单工厂模式
    简介在软件开发过程中,设计模式是一种被广泛应用的实践,它是通过总结、归纳和提炼出软件设计经验,从而使得设计更加优雅、高效。简单工厂模式是设计模式中最基本、最简单的一种模式,它能够有效地封装对象的创建过程,简化代码结构。简单工厂模式又称为静态工厂方法模式,它是通过定义一......
  • 【MySQL--09】表的内连和外连
    【MySQL--09】表的内连和外连表的连接分为内连接和外连接1.1内连接内连接实际上就是利用where子句对两种表形成的笛卡尔积进行筛选,我们之前所用的查询都是内连接,也是在开发过程中使用的最多的连接查询。select字段from表1innerjoin表2on连接条件and其他条件;备注:前......
  • hdu:Party(2-SAT)
    ProblemDescription有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n个人同时列席?Inputn:表示有n对夫妻被邀请(n<=1000)m:表......
  • 力扣---872. 叶子相似的树
    请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个 叶值序列。 举个例子,如上图所示,给定一棵叶值序列为 (6,7,4,9,8) 的树。如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 root1和 root2......
  • 力扣---104. 二叉树的最大深度
    给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例:给定二叉树[3,9,20,null,null,15,7],3/\920/\157返回它的最大深度 3。来源:力扣(LeetCode)链接:https://leetcode......
  • 5.8-5.14
    C1.PokémonArmy(easyversion)Problem-1420C1-Codeforces线性dp呃啊啊啊啊啊啊啊太久没写dp了,下周开始要把重点放到算法上意识到是个dp后就很简单了,状态转移方程也很好写出\[\begin{cases}f[i][0]\=\max(f[i-1][0],\f[i-1][1]+num[i]\\f[i][1]\=\max(f[i-1][......
  • hdu:Let's go home(2-SAT)
    ProblemDescription小时候,乡愁是一枚小小的邮票,我在这头,母亲在那头。——余光中集训是辛苦的,道路是坎坷的,休息还是必须的。经过一段时间的训练,lcy决定让大家回家放松一下,但是训练还是得照常进行,lcy想出了如下回家规定,每一个队(三人一队)或者队长留下或者其余两名队员同时留下;每......
  • citect2018R2报警函数练习1-做一个简单的报警显示页面
    这一个笔记我在新浪博客记录过,地址是Citect2018R2报警函数练习1-做一个简单的报警显示页面_来自金沙江的小鱼_新浪博客(sina.com.cn) 这两天看citect一些文档,想着练习一下Cicode的报警函数。新建一个Unity项目,简单的配一下硬件 写简单的程序新建一个Citect2018R2程序,使......
  • Java设计模式-桥接模式
    简介桥接模式(BridgePattern)是一种结构性设计模式,它的主要作用是将抽象部分和实现部分解耦,使它们可以独立变化而不会互相影响。桥接模式最早由GoF(GangofFour)提出,在《设计模式》一书中有详细的介绍。桥接模式和其他设计模式的区别在于它关注的是如何将抽象和实现分离,从而达到灵......