C solution


  • 0
    M

    double* averageOfLevels(struct TreeNode* root, int* returnSize) {
    int ret_alloc_size = 10;
    int nodes_alloc_size = 10;
    struct TreeNode** cur_nodes = (struct TreeNode**) malloc(nodes_alloc_size * sizeof(struct TreeNode*));
    struct TreeNode** next_nodes = (struct TreeNode**) malloc(nodes_alloc_size * sizeof(struct TreeNode*));
    struct TreeNode** swap_nodes = NULL;
    struct TreeNode* node = NULL;
    int cur_len, next_len;
    int n;
    double* ret = (double*) malloc(ret_alloc_size * sizeof(double));
    double sum = 0;

    *returnSize = 0;
    next_nodes[0] = root;
    next_len = 1;
    
    while (next_len) {
        // swap cur and next nodes
        swap_nodes = cur_nodes;
        cur_nodes = next_nodes;
        next_nodes = swap_nodes;
        cur_len = next_len;
        next_len = 0;
    
        n = cur_len;
        sum = 0;
        while (cur_len) {
            node = cur_nodes[--cur_len];
            sum += node->val;
            
            // check nodes array size enough
            if ((next_len + 2) > nodes_alloc_size) {
                nodes_alloc_size = nodes_alloc_size + nodes_alloc_size / 2;
                next_nodes = (double*) realloc(next_nodes, nodes_alloc_size * sizeof(double));
                cur_nodes = (double*) realloc(cur_nodes, nodes_alloc_size * sizeof(double));
            }
            
            if (node->left) {
                next_nodes[next_len++] = node->left;
            }
            if (node->right) {
                next_nodes[next_len++] = node->right;
            }
        }
        // current layer all sum
        
        // check ret array size enough
        if (((*returnSize) + 1) > ret_alloc_size) {
            ret_alloc_size = ret_alloc_size + ret_alloc_size / 2;
            ret = (double*) realloc(ret, ret_alloc_size * sizeof(double));
        }
        
        // add average to ret
        ret[(*returnSize)++] = sum / n;
    }
    free(cur_nodes);
    free(next_nodes);
    return ret;
    

    }


Log in to reply
 

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