[508] Most Frequent Subtree Sum

雖然我不是很確定我在寫什麼(?)

而且還有點搞錯題目的意思（？）

還有一咪咪try & error

但是管它的我覺得寫起來還蠻漂亮的啊？XD （真敢講XD）

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* struct TreeNode *left;

* struct TreeNode *right;

* };

*/

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int idx;

int dfs(struct TreeNode* root,int *sum)

{

if (root == NULL)

return 0;

int left=0 , right=0;

left = dfs(root->left, sum);

right = dfs(root->right, sum);

sum[idx++] += root->val + left + right;

return root->val + left + right;

}

int comp(const void *a, const void *b)

{

return (*(int*)a- *(int*)b);

}

int* findFrequentTreeSum(struct TreeNode* root, int* returnSize) {

int *sum = calloc (100000, sizeof(int));

idx=0;

dfs(root, sum);

qsort(sum,idx, sizeof (int),comp);

int *count = calloc (idx, sizeof(int));

int max = 0;

for (int i=0;i<idx; i++)

{

int start = i, end = i;

while(end < idx && sum[end]==sum[end+1])

end++;

count[i] = (end-start +1);

if (count[i]> max)

max = count[i];

// printf("%d\n", sum[i]);

}

*returnSize= 0;

for (int i=0; i<idx;i++)

{

if (count[i]== max)

count[(*returnSize)++] = sum[i];

}

return count;

}