1448. Count Good Nodes in Binary Tree

📘 題目敘述

給你一棵二元樹的根節點 root。

如果在從根節點到某個節點 X 的路徑上，沒有任何節點的值大於 X 的值，則稱節點 X 為 good。

請回傳二元樹中 good 節點的數量。

條件限制

• 二元樹中的節點數量在範圍 [1, 10^5]
• -10^4 <= Node.val <= 10^4

🧠 解題思路

我在走訪樹的時候，只要能一直知道一件事就夠了：

從根走到目前這個節點的路徑上，出現過的最大值是多少。

我把這個「路徑最大值」用一個參數 best 帶進遞迴。

當我走到某個節點 root：

• 如果 root->val >= best，代表它不小於路徑上任何一個值，所以它就是 good node，count++

接著我往左右子樹遞迴時，要更新路徑最大值：

• 新的路徑最大值就是 max(best, root->val)

這樣每個節點只需要被走一次，就能判斷它是不是 good。

所有變數

• root：題目輸入的樹根節點（也是 check 目前檢查的節點）
• count：good nodes 的數量（全域累加，最後回傳）
• best：從根到目前節點這條路徑上的最大值

🪜 主要流程步驟

1. 用 best 代表「走到目前為止的路徑最大值」

我設計 check(root, best)，其中 best 永遠代表「從根到 root 的路徑上出現過的最大值」。

2. 每到一個節點就判斷它是不是 good

如果 root->val >= best，就代表路徑上沒有比它更大的值，所以它是 good node，直接 count++。

3. 往左右子樹遞迴時更新 best

往下走之後，路徑最大值要包含目前節點，所以我用 max(root->val, best) 把它傳給下一層，確保子節點判斷時拿到的是正確的路徑最大值。

4. 從根開始呼叫 check，最後回傳 count

在 goodNodes(root) 中：

• 我用 check(root, root->val) 讓起始路徑最大值先等於根本身
• 走完整棵樹後回傳 count

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int count = 0;
    void check(TreeNode* root, int best) {
        if (root) {
            if (root->val >= best) {
                count++;
            }
            check(root->left, max(root->val, best));
            check(root->right, max(root->val, best));
        } else {
            return;
        }
    }
    int goodNodes(TreeNode* root) {
        check(root, root->val);
        return count;
    }
};

🔗 題目連結

https://leetcode.com/problems/count-good-nodes-in-binary-tree/