I solved this problem using recursion with no queues. Post my code in C. One take!


  • 0
    S

    int max_2(int x,int y)
    {
    return x>y?x:y;
    }
    int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    int **left_value,**right_value,**root_value;
    int *left_col,*right_col,*root_col;
    int i,left_len,right_len,root_len;

    if(root == NULL)
    {
        *columnSizes = NULL;
        *returnSize = 0;
        return NULL;
    }
    
    left_value = levelOrder(root->left,&left_col,&left_len);
    right_value= levelOrder(root->right,&right_col,&right_len);
    
    root_len = max_2(left_len,right_len) + 1;
    
    root_value = (int**)malloc(root_len*sizeof(int*));
    root_col = (int*)malloc(root_len*sizeof(int));
    
    root_value[0] = (int*)malloc(sizeof(int));
    root_value[0][0] = root->val;
    root_col[0] = 1;
    
    for(i=1;i<=left_len&&i<=right_len;i++)
    {
        root_col[i] = left_col[i-1] + right_col[i-1];
        root_value[i] = (int*)malloc(root_col[i]*sizeof(int));
        memcpy(root_value[i],left_value[i-1],left_col[i-1]*sizeof(int));
        memcpy(root_value[i]+left_col[i-1],right_value[i-1],right_col[i-1]*sizeof(int));
        free(left_value[i-1]);
        free(right_value[i-1]);
    }
    while(i<=left_len)
    {
        root_col[i] = left_col[i-1];
        root_value[i] = (int*)malloc(root_col[i]*sizeof(int));
        memcpy(root_value[i],left_value[i-1],left_col[i-1]*sizeof(int));
        free(left_value[i-1]);
       
        i++;
    }
    while(i<=right_len)
    {
        root_col[i] = right_col[i-1];
        root_value[i] = (int*)malloc(root_col[i]*sizeof(int));
        memcpy(root_value[i],right_value[i-1],right_col[i-1]*sizeof(int));
        free(right_value[i-1]);
        
        i++;
    }
    
    free(left_value);
    free(right_value);
    free(left_col);
    free(right_col);
    
    *columnSizes = root_col;
    *returnSize  = root_len;
    return root_value;
    

    }


Log in to reply
 

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