Problem
Given the root of a binary tree, a node is called good if there is no node on the path from the root to that node with a value greater than the node's value.Return the number of good nodes in the binary tree.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
root:
3
/ \
1 4
/ / \
3 1 5Output
4Example 2
Input
root:
3
/ \
3 4
/ \ \
2 4 5Output
4Solution
This solution uses Depth-First Search (DFS). We pass the maximum value encountered on the path from the root to the current node.A node is a good node if its value is greater than or equal to the maximum value seen before reaching that node. We calculate
newMaxValue using the current node's value and pass it to both subtrees.
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int maxValue) {
if (node == null) {
return 0;
}
int newMaxValue = Math.max(maxValue, node.val);
return (node.val >= maxValue ? 1 : 0)
+ dfs(node.left, newMaxValue)
+ dfs(node.right, newMaxValue);
}
}Complexity
Each node is visited exactly once, so the time complexity isO(n), where n is the number of nodes in the binary tree.
The DFS recursion uses space proportional to the height of the tree, so the extra space complexity is
O(h), where h is the height of the tree.