Count Good Nodes in Binary Tree
MediumTrees
Given the root of a binary tree, return the number of *good* nodes in it.
A node is good if no node on the path from the root down to it (excluding the node itself) has a value greater than it. In other words, the node's value is at least the maximum value seen above it. Equal values count as good, and the root is always good.
Trees are written in level order: values are listed level by level, left to right, and null marks a missing child (trailing nulls are omitted).
Example 1
- Input:
- root = [2,null,4,10,8,4]
- Output:
- 4
- Explanation
- The root is always good. 4 clears the 2 above it, and 10 and 8 both clear the running maximum of 4. Only the last 4 fails, because 10 sits above it on its path.
Example 2
- Input:
- root = [5,3,8,6,null,9,1]
- Output:
- 4
- Explanation
- 6 is good even though its parent 3 is smaller: what matters is the largest value on its path, which is 5. 3 and 1 are below 5 and 8 respectively, so the good nodes are 5, 6, 8 and 9.
Example 3
- Input:
- root = [-1,-2,-1,-3,null,-1]
- Output:
- 3
- Explanation
- The root is good, and so are the right child -1 and its child -1, since equalling the running maximum is allowed. -2 and -3 both fall below -1.
Constraints
- The number of nodes is in the range
[1, 10^5] -10^4 <= Node.val <= 10^4- The tree height is at most
500