1448. Count Good Nodes in Binary Tree¶
题目信息¶
- 题号:
1448
- 难度:
Medium
- 主题:
二叉树、深度优先搜索、路径最大值
- 原题:
- 重点:
若从根到当前节点的路径上不存在值严格大于当前节点的节点,则当前节点为好节点
题目重述¶
给定一棵非空二叉树。对于节点 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
解释:根到自身的路径上没有其他节点。