Description
Count nodes whose value is at least every value on the path from the root to that node. The root is always good. Examples use level-order arrays.
Solution
def good_nodes(root):
if not root:
return 0
stack = [(root, root.val)]
count = 0
while stack:
node, highest = stack.pop()
if node.val >= highest:
count += 1
highest = max(highest, node.val)
if node.right:
stack.append((node.right, highest))
if node.left:
stack.append((node.left, highest))
return countExamples
Example 1
- Input
[[3,1,4,3,null,1,5]]- Output
4
The root, left 3, right 4, and 5 are good.
Example 2
- Input
[[3,3,null,4,2]]- Output
3
Equal values are allowed; the 2 is blocked by a larger ancestor.
Example 3
- Input
[[1]]- Output
1
The root is good.
Approach
Carry the maximum seen on the current root-to-node path. Count a node if its value meets that maximum, then pass the updated maximum separately to its children.
Time & space
O(n) time and O(h) auxiliary space for an explicit DFS stack, where n is the node count and h is tree height.