Count Good Nodes in Binary Tree
Problem
A node is good if no node on the path from the root to it has a greater value. Return the number of good nodes.
Example 1
Input: [3, 1, 4, 3, null, 1, 5] Output: 4
Nodes 3 (root), 4, 5 and the lower 3.
Test cases
Case 1
Input: [3,1,4,3,null,1,5] Expected: 4
Case 2
Input: [3,3,null,4,2] Expected: 3
Case 3
Input: [1] Expected: 1
View solutionHide solution1 approach
1. DFS carrying the path maximum
Time O(n)Space O(h)
A node is good if its value ≥ the maximum seen from the root to it.
function goodNodes(root) { const dfs = (node, max) => { if (!node) return 0; const good = node.val >= max ? 1 : 0; max = Math.max(max, node.val); return good + dfs(node.left, max) + dfs(node.right, max); }; return dfs(root, -Infinity);}