625. Count Good Nodes in Binary Tree
Call a node of a binary tree good when nothing above it beats it: on the path from the root down to that node, no node carries a value strictly greater than the node's own value. The root is always good (its path is just itself), and ties are fine — an ancestor with an equal value does not disqualify a node.
Your function receives root, the root node of a binary tree, and must return the number of good nodes in the whole tree as an integer.
Example 1:
Input: root = [3, 1, 4, 3, null, 1, 5]
Output: 4
Explanation: Good nodes: the root 3, the deep-left 3 (its path 3 → 1 → 3 has maximum 3, a tie), the 4 (path max before it is 3), and the 5. Both 1s sit below a 3, so they fail.
Example 2:
Input: root = [3, 3, null, 4, 2]
Output: 3
Explanation: The root 3, its left child 3 (equal values count), and the 4 are good. The 2 has the 3s above it, so it is not.
Example 3:
Input: root = [1]
Output: 1
Explanation: A lone root is always good.
Constraints:
- 1 ≤ number of nodes ≤ 10⁵
- -10⁴ ≤ Node.val ≤ 10⁴
Hints:
A node only cares about one number from its entire ancestry: the largest value seen so far on the way down. Everything else about the path is irrelevant.
Do a depth-first traversal that carries that running maximum as a parameter. At each node compare, count, update the maximum, and recurse — one visit per node, O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 1, 4, 3, null, 1, 5]
Expected output: 4