[102] Binary Tree Level Order Traversal (TBC)

狀況很差
莫再提 T__T
有機會的話用add queue的方式寫一次看看 QQ


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    struct TreeNode *queue[10000];
    int i=0;
    int **retArray = malloc(sizeof(int *)*10000);
    *columnSizes = malloc(sizeof(int *)*10000);

    *returnSize=0;
    if(root == NULL)
        return retArray;
    struct TreeNode* ptr = root;
    int head=0;
    int tail=1;
    queue[head]= root;
    int level = 0;
    int nextcount = 0,  cur_count=1;
    while(head < tail/*ptr != NULL*/)
    {
        retArray[level] = malloc(sizeof(int) * 10000);
        for (i=0;i<cur_count && head < tail;i++)
        {
            if(ptr->left!=NULL)
            {
                queue[tail++]=ptr->left;
                nextcount++;
            }
            if(ptr->right!=NULL)
            {
                queue[tail++]=ptr->right;
                nextcount++;
            }
            retArray[level][i] = ptr->val;

            ptr = queue[++head];
        }

        (*columnSizes)[level++] = cur_count;
        cur_count = nextcount;
        nextcount = 0;
    }
    *returnSize=level;  
    return retArray;
}