1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h>
5
6typedef struct TreeNode {
7    int val;
8    struct TreeNode *left, *right;
9} TreeNode;
10
11typedef struct {
12    int *sums;
13    int size, capacity;
14} ResultSet;
15
16typedef struct {
17    int key, value;
18} Pair;
19
20typedef struct {
21    Pair *data;
22    int size;
23} HashMap;
24
25void initHashMap(HashMap *map) {
26    map->data = (Pair *)malloc(1000 * sizeof(Pair)); // dynamic max size
27    map->size = 0;
28}
29
30int findIndex(HashMap *map, int key) {
31    for (int i = 0; i < map->size; i++) {
32        if (map->data[i].key == key) {
33            return i;
34        }
35    }
36    return -1;
37}
38
39void put(HashMap *map, int key, int value) {
40    int index = findIndex(map, key);
41    if (index == -1) { // new key
42        map->data[map->size].key = key;
43        map->data[map->size].value = value;
44        map->size++;
45    } else { // existing key
46        map->data[index].value += value;
47    }
48}
49
50int get(HashMap *map, int key) {
51    int index = findIndex(map, key);
52    return index != -1 ? map->data[index].value : 0;
53}
54
55int postOrder(TreeNode *root, HashMap *map) {
56    if (!root) return 0;
57    int left = postOrder(root->left, map);
58    int right = postOrder(root->right, map);
59    int sum = root->val + left + right;
60    put(map, sum, 1);
61    return sum;
62}
63
64ResultSet findFrequentTreeSum(TreeNode* root) {
65    HashMap map;
66    initHashMap(&map);
67    postOrder(root, &map);
68    int maxFreq = 0;
69    for (int i = 0; i < map.size; i++) {
70        if (map.data[i].value > maxFreq) {
71            maxFreq = map.data[i].value;
72        }
73    }
74    ResultSet res;
75    res.size = 0;
76    res.capacity = 100;
77    res.sums = (int *)malloc(res.capacity * sizeof(int));
78    for (int i = 0; i < map.size; i++) {
79        if (map.data[i].value == maxFreq) {
80            if (res.size >= res.capacity) {
81                res.capacity *= 2;
82                res.sums = (int *)realloc(res.sums, res.capacity * sizeof(int));
83            }
84            res.sums[res.size++] = map.data[i].key;
85        }
86    }
87    return res;
88}
89
90int main() {
91    // Binary tree creation and test
92    TreeNode node1 = {5, NULL, NULL};
93    TreeNode node2 = {2, NULL, NULL};
94    TreeNode node3 = {-3, NULL, NULL};
95    node1.left = &node2;
96    node1.right = &node3;
97    ResultSet result = findFrequentTreeSum(&node1);
98    for (int i = 0; i < result.size; i++) {
99        printf("%d ", result.sums[i]);
100    }
101    free(result.sums);
102    return 0;
103}
104

1#include <unordered_map>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    unordered_map<int, int> freqMap;

    int dfs(TreeNode* node) {
        if (!node) return 0;
        int leftSum = dfs(node->left);
        int rightSum = dfs(node->right);
        int sum = node->val + leftSum + rightSum;
        freqMap[sum]++;
        return sum;
    }

public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> maxFreqSums;
        int maxFreq = 0;
        for (const auto& entry : freqMap) {
            if (entry.second > maxFreq) {
                maxFreq = entry.second;
                maxFreqSums = {entry.first};
            } else if (entry.second == maxFreq) {
                maxFreqSums.push_back(entry.first);
            }
        }
        return maxFreqSums;
    }
};

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(2);
    root->right = new TreeNode(-3);
    Solution sol;
    vector<int> result = sol.findFrequentTreeSum(root);
    for (int val : result) {
        cout << val << " ";
    }
    return 0;
}