Share my C solution(use one queue)


  • 0
    J
    int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    if(returnSize == NULL)
    	return NULL;
    if(root == NULL){
    	*returnSize = 0;
    	return NULL;
    }
    *columnSizes = (int *)malloc(sizeof(int) * 1000);
    memset(*columnSizes,0,sizeof(*columnSizes));
    struct TreeNode *queue[2000], *temp;
    int first = 0, end = 0;
    int **result = (int **)malloc(sizeof(int *) * 1000);
    int i = 1, j = 0, k = 0, m = 0, n = 0;
    /* root enter queue */
    queue[end++] = root;
    while(end > first)
    {
    	result[k] = (int *)malloc(sizeof(int) * 1000);
    	m = 0;
    	/* use i to control the number of elements in each level */
    	for(j = 0; j < i && end > first; j++){
    		/* out the front */
            temp = queue[first++];
    		result[k][m++] = temp -> val;
    		/* lchild and rchild enter the queue */
    		if(temp -> left){
    			queue[end++] = temp -> left;
    			n++;
    		}
    		if(temp -> right){
    			queue[end++] = temp -> right;
    			n++;
    		}
    	}
    	(*columnSizes)[k++] = m;
    	if(!(i = n))
    		break;
    	n = 0;
    }
    *returnSize = k;
    return result;
    

    }

    Although only use one queue,but should really be careful of the queue size,too small can't work out ;)

    At first,I try to create a Complete Binary Tree by record every node into queue(even NULL) and use i = 1,2,4,8,16,... to figure out the number of elements in one level.But as you see,since it obviously a o(2^n),the queue quickly blows up and it takes me nearly half the day to find the bug...; (

    Already seen a solution use 2 queues,I think it's obviously better because you don't need too much space since you can put elements of each level from the very beginning of the array every time,comparing with mine which wastes more and more space as the level grows since the space of my array can only be used one time.

    Still share my code,wish it can help you ; )


  • 0
    A

    your variable 'm' and 'j' do the same thing in for loop, just using one of them


Log in to reply
 

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