C solution, hash table, 9ms


  • 1
    S
    /**
     * 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);
    		HASH_ADD_INT(hash, key, s);
    	}
    	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;
    }
    
    

Log in to reply
 

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