⚡Flashcard Drill➔
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

  1. Do a DFS carrying the maximum value seen along the path.
  2. At each node, if node.val >= max_so_far, the node is good.
  3. Then recurse with max(max_so_far, node.val).
  4. 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 -infinity is 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems