1448. Count Good Nodes in Binary Tree

題目網址：https://leetcode.cn/problems/count-good-nodes-in-binary-tree/

題意：給一 BT 的 root, 返回 BT 中 Good node 的個數。

Good node x 的定義：從 root 到 x 所經過的 node 中, 沒有任何 node.val 大於 x.val。

Solution：

想法：利用 DFS, 在 DFS 過程中維護當前路徑的最大值 curMax。若 node->val ≥ curMax, 則更新 maxCur, 並返回 1 + 左子樹的 good node 數 + 右子樹的 good node 數, 那個 1 是把當前 node 視為 good node

class Solution {
public:
    int goodNodes(TreeNode* root) {
        return dfs(root, root->val);
    }

private:
    // dfs(root, curMax) 返回 root 到 node 的 path 上總共有幾個 good node
    int dfs(TreeNode* node, int curMax){
        if (!node) {
            return 0;
        }

        if (node->val >= curMax) {
            curMax = max(curMax, node->val);
            return 1 + dfs(node->left, curMax) + dfs(node->right, curMax);
        }

        return dfs(node->left, curMax) + dfs(node->right, curMax);
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ 取決於遞迴深度, worse case：skew tree