# C solution, hash table, 9ms

• ``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
struct hash_t {
int key;
int val;
UT_hash_handle hh;
};

struct hash_t *hash = NULL;

struct hash_t *hash_node_new(int key, int val)
{
struct hash_t *s;
s = malloc(sizeof(struct hash_t));
s->key = key;
s->val = val;

return s;
}

int treeSum(struct TreeNode *root, int *num)
{
int sum = 0;
struct hash_t *s = NULL;
if(!root)	return 0;

sum = treeSum(root->left, num) + treeSum(root->right, num) + root->val;

HASH_FIND_INT(hash, &sum, s);
if(s){
s->val += 1;
}else{
s = hash_node_new(sum, 1);
}
if(s->val > *num)	*num = s->val;

return sum;
}

int* findFrequentTreeSum(struct TreeNode* root, int* returnSize) {
int num = 0, n=0, *ret, i=0;

treeSum(root, &num);
struct hash_t *s;

for(s = hash; s != NULL; s=s->hh.next)
{
if(s->val == num)	n++;
}
*returnSize = n;
ret = malloc(sizeof(int) * n);
for(s = hash, i=0; s != NULL; s=s->hh.next)
{
if(s->val == num)	ret[i++] = s->key;
}
HASH_CLEAR(hh, hash);

return ret;
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.