LeetCode //C - 1448. Count Good Nodes in Binary Tree

1448. Count Good Nodes in Binary Tree

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.
?

Example 1:

Input root = [3,1,4,3,null,1,5]
Output 4
Explanation:
Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input root = [3,3,null,4,2]
Output 3
Explanation: Node 2 -> (3, 3, 2) is not good, because “3” is higher than it.

Example 3:

Input root = [1]
Output 1
Explanation: Root is considered as good.

Constraints:

• The number of nodes in the binary tree is in the range $[1,10^5]$.
• Each node’s value is between $[?10^4,10^4]$.

From: LeetCode
Link: 1448. Count Good Nodes in Binary Tree

---

Solution:

Ideas：

In this code, goodNodes is the main function that invokes countGoodNodes, a helper function that does the actual DFS traversal. It takes two parameters: the current node and the maximum value found in the path from the root to this node. If the current node is not less than the maximum value, we count it as a good node and update the maximum value. Then, we recursively count the good nodes in both the left and right subtrees.

The countGoodNodes function will be called with the root node and INT_MIN to start the count, as initially, there is no maximum value on the path from the root. The INT_MIN is a macro that specifies that an integer variable cannot store any value below this limit, ensuring that the root node is always considered good.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int countGoodNodes(struct TreeNode* node, int maxVal) {
    if (node == NULL) return 0;
    int count = 0;
    if (node->val >= maxVal) {
        count = 1; // This node is good
        maxVal = node->val; // Update the maxVal with the current node's value
    }
    // Count good nodes in the left and right subtrees
    count += countGoodNodes(node->left, maxVal);
    count += countGoodNodes(node->right, maxVal);
    return count;
}

int goodNodes(struct TreeNode* root) {
    return countGoodNodes(root, INT_MIN); // Start with the smallest integer as the initial max value
}