Đếm nút gốc giá trị lớn nhất trong cây nhị phân C++

Cho cây nhị phân. Đếm số nút có giá trị ≥ tất cả các nút con cháu của nó (maximal value roots).

Thuật toán (DFS post-order)

• DFS trả về giá trị lớn nhất trong cây con.
• Tại nút: nếu node->val >= max(left_max, right_max) → count++.
• Trả về max(node->val, left_max, right_max).

Ví dụ triển khai (C++)

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

struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int d) : val(d), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int ret = 0;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int l = dfs(node->left);
        int r = dfs(node->right);
        if (node->val >= max(l, r)) ret++;
        return max({node->val, l, r});
    }
    int solve(TreeNode* root) {
        ret = 0; dfs(root); return ret;
    }
};

int main() {
    Solution ob;
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(4);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(5);
    cout << ob.solve(root);
    return 0;
}

Đầu ra

4