Count Good Nodes in a Binary Tree (LeetCode 1448) – Problem Explanation and Java/C++ Solutions

At the start the author briefly mentions the upcoming May Day holiday and a temporary ticket‑purchasing issue on the 12306 platform.

The core of the article is LeetCode problem 1448, which asks for the number of "good" nodes in a binary tree. A node X is considered good if no node on the path from the root to X has a value greater than X.

Example 1: input root = [3,1,4,3,null,1,5] → output 4 . The good nodes are the root (3), the node 4, the node 5, and the left‑most 3.

Example 2: input root = [3,3,null,4,2] → output 3 . Node 2 is not good because a larger value (3) appears earlier on its path.

Constraints: the number of nodes is in the range [1, 10^5] and each node value is between -10^4 and 10^4.

Problem analysis – The task can be solved with a depth‑first search (DFS) that carries the maximum value seen so far on the current root‑to‑node path. When the current node’s value is greater than or equal to this maximum, it is counted as a good node.

DFS pseudo‑logic: traverse the tree, update the path maximum, and accumulate the count of good nodes.

Java implementation:

public int goodNodes(TreeNode root) {
    return dfs(root, Integer.MIN_VALUE);
}

private int dfs(TreeNode root, int maxV) {
    if (root == null) return 0;
    int left = dfs(root.left, Math.max(root.val, maxV));
    int right = dfs(root.right, Math.max(root.val, maxV));
    return left + right + (root.val < maxV ? 0 : 1);
}

C++ implementation:

int goodNodes(TreeNode *root) {
    return dfs(root, INT_MIN);
}

int dfs(TreeNode *root, int maxV) {
    if (root == nullptr) return 0;
    int left = dfs(root->left, max(root->val, maxV));
    int right = dfs(root->right, max(root->val, maxV));
    return left + right + (root->val < maxV ? 0 : 1);
}

The author, 王一博 (Bo Ge), is a seasoned algorithm enthusiast who has solved over 2,000 problems across various platforms and writes algorithm explanations for a public account.