Count Good Nodes in Binary Tree
- 1 min read
- LC-Medium
- Binary Tree
3 years ago
Solution
- Just do a Depth-first Search on the tree while keeping a track of the maximum value seen in that particular path
- If the current node we're at's value is greater than or equal to the max in the path, increment our counter variable.
- Update the max value variable as we recur down
| Time | Space | Explanation |
|---|---|---|
O(n) | O(log n) |
def goodNodes(self, root: TreeNode) -> int:
ans = 0
def dfs(root, max_in_path):
nonlocal ans
if root:
if root.val >= max_in_path:
ans += 1
max_in_path = max(max_in_path, root.val)
dfs(root.left, max_in_path)
dfs(root.right, max_in_path)
dfs(root, -math.inf)
return ans