NeetCode #441LC-1448MediumTreesNC 150NC 250
← Back to All Problems#441 · #1448 · Count Good Nodes in Binary Tree(统计二叉树中好节点的数目)
📌 Problem Statement & Constraints
Given a binary tree, a node
X is good if, on the path from the root to X, there is no node with a value greater than X.val. Return the number of good nodes. Constraints: the number of nodes is in [1, 10^5], -10^4 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- Do a DFS carrying the maximum value seen along the path.
- At each node, if
node.val >= max_so_far, the node is good. - Then recurse with
max(max_so_far, node.val). - The root is always good, since the initial maximum is
-infinity.
💻 Benchmark Python3 Implementation
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(node: Optional[TreeNode], mx: int) -> int:
if not node:
return 0
cnt = 1 if node.val >= mx else 0 # good if no greater ancestor
mx = max(mx, node.val) # update for the children
return cnt + dfs(node.left, mx) + dfs(node.right, mx)
return dfs(root, float("-inf"))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
>instead of>=: a node equal to the path maximum is still good. - Initialising the maximum to 0: negative values are allowed, so
-infinityis required, otherwise negative nodes would be wrongly rejected. - Comparing against the immediate parent instead of the path maximum: the condition is about the whole path.
- Not updating the maximum before recursing: the children would see the stale value.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.