Tổng cây con xuất hiện nhiều nhất trong C++

Cho gốc cây, tìm tổng cây con xuất hiện nhiều nhất. Tổng cây con của một nút là tổng tất cả giá trị nút trong cây con gốc tại nút đó (kể cả chính nút). Nếu có nhiều giá trị cùng tần suất cao nhất, trả về tất cả. Ví dụ: [5,2,-5] → [2] vì 2 xuất hiện 2 lần, -5 chỉ 1 lần.

Giải thuật

• Hai map: m (tần suất → danh sách tổng), freq (tổng → tần suất).
• Hàm solve(node):
  • Nếu node == null trả về 0.
  • leftSum = solve(node->left), rightSum = solve(node->right).
  • currSum = node->val + leftSum + rightSum.
  • Nếu freq chưa có currSum: thêm vào m[1], freq[currSum] = 1.
  • Ngược lại: tăng freq[currSum], thêm vào m[freq[currSum]].
  • Trả về currSum.
• Hàm chính: nếu root == null trả về rỗng; gọi solve(root); trả về danh sách cuối của m.

Ví dụ mã C++

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

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

class Solution {
public:
    map<int, vector<int>> m;
    map<int, int> freq;
    int solve(TreeNode* node) {
        if (!node) return 0;
        int leftSum = solve(node->left);
        int rightSum = solve(node->right);
        int currSum = node->val + leftSum + rightSum;
        if (!freq.count(currSum)) {
            m[1].push_back(currSum);
            freq[currSum] = 1;
        } else {
            freq[currSum]++;
            m[freq[currSum]].push_back(currSum);
        }
        return currSum;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        m.clear(); freq.clear();
        if (!root) return {};
        solve(root);
        return m.rbegin()->second;
    }
};

Đầu vào

[5,2,-5]

Đầu ra

[2, ]