Đếm nút tốt trong cây nhị phân (Count Good Nodes in Binary Tree) trong C++

Cho cây nhị phân. Nút X gọi là tốt (good) nếu trên đường đi từ gốc đến X không có nút nào có giá trị lớn hơn X. Đếm số nút tốt.

Ví dụ

Đầu ra: 4 (các nút tô màu).

Thuật toán DFS truyền giá trị lớn nhất trên đường đi

1. Hàm dfs(node, maxVal): maxVal là giá trị lớn nhất từ gốc đến cha của node.
2. Nếu node->val >= maxVal → node tốt, tăng đếm.
3. Gọi đệ quy cho con trái/phải với newMax = max(maxVal, node->val).
4. Khởi tạo dfs(root, INT_MIN).

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(NULL), right(NULL) {}
};

class Solution {
    int ans = 0;
    void dfs(TreeNode* node, int mx) {
        if (!node) return;
        if (node->val >= mx) ++ans;
        int nmx = max(mx, node->val);
        dfs(node->left, nmx);
        dfs(node->right, nmx);
    }
public:
    int goodNodes(TreeNode* root) {
        dfs(root, INT_MIN);
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt mỗi nút một lần.
• Không gian: O(H) - ngăn xếp đệ quy.

Kết quả kiểm thử

Đầu vào: {3,1,4,3,NULL,1,5}
Đầu ra: 4