The problem
A node is good if no node on the path from the root down to it has a larger value. Given the root of a binary tree, return the number of good nodes.
Examples
01
- Input
root = [3, 1, 4, 3, null, 1, 5]
- Output
4
02
- Input
root = [3, 3, null, 4, 2]
- Output
3
03
- Input
root = [1]
- Output
1
Constraints
- 1 ≤ number of nodes ≤ 10⁵
- −10⁴ ≤ Node.val ≤ 10⁴
The idea
Whether a node is good depends only on the largest value above it. So carry that number down.
A depth-first search passes each child best, the largest value on the path so far. A node is good when its value is at least best; it then passes down the larger of best and its own value. The root is always good.
- Time
- O(n)
- Space
- O(h)
Solution · every language run against every case
class Solution: def goodNodes(self, root: TreeNode) -> int: def count(node, best): # best: the largest value on the path from the root if not node: return 0 good = 1 if node.val >= best else 0 best = max(best, node.val) return good + count(node.left, best) + count(node.right, best) return count(root, root.val)