#1448
Count Good Nodes in Binary Tree
Medium DFS carrying the path maximum
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A node is "good" if no node on the path from the root to it has a greater value. Count the good nodes.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: nodes with no bigger node above them on their path.
Why this works: pass the maximum seen so far down the recursion.
Example: 3 (1 (3), 4 (1, 5))
good: 3, 3 (path 3,1,3), 4, 5 → 4✦Hints open one at a time
Pass the maximum value seen so far down the recursion.
A node is good if its value is >= that maximum.
↗Approach
dfs(node, maxSoFar): count 1 if node.val >= maxSoFar, then recurse with max(maxSoFar, node.val).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, Integer.MIN_VALUE);
}
private int dfs(TreeNode n, int maxSoFar) {
if (n == null) return 0;
int good = n.val >= maxSoFar ? 1 : 0;
int m = Math.max(maxSoFar, n.val); // passed by value: no undo needed
return good + dfs(n.left, m) + dfs(n.right, m);
}
}!Common mistake
Using a shared variable for the maximum and not restoring it when returning from a subtree.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon