1448. Count Good Nodes in Binary Tree

题目信息

题号:

1448

难度:

Medium

主题:

二叉树、深度优先搜索、路径最大值

原题:

LeetCode 1448

重点:

若从根到当前节点的路径上不存在值严格大于当前节点的节点,则当前节点为好节点

题目重述

给定一棵非空二叉树。对于节点 X,若从根节点到 X 的路径上所有节点值都不大于 X.val,则称 X 为好节点。

请返回树中好节点的数量。路径包含根节点和当前节点自身。

树中节点数位于 [1, 10^5],-10^4 <= Node.val <= 10^4。

自建示例

与路径最大值相等的节点也属于好节点:

输入:root = [3,1,4,3,null,1,5]
输出:4
解释:值为 3 的根、左下方值为 3 的节点、右孩子 4 和节点 5 都不小于各自路径上的先前节点。

单节点树的根必然是好节点:

输入:root = [-2]
输出:1
解释:根到自身的路径上没有其他节点。