103. Binary Tree Zigzag Level Or

同普通level order访问逻辑一样,只是在保存节点的时候，偶数层从左向右保存，奇数层从右向左保存：

            if(*returnSize%2 == 0)
                ret[*returnSize][i] = node->val;
            else 
                ret[*returnSize][size-i-1] = node->val;

/**
 * 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().
 */
struct queue{
    struct ListNode * dummy;
    struct ListNode * last;

};

struct queue * init_queue()
{
    struct queue * q = calloc(1, sizeof(struct queue));
    q->dummy = calloc(1, sizeof(struct ListNode));
    q->last = q->dummy;

    return q;

}

void enqueue(struct queue *q, void * val){
    struct ListNode * node = calloc(1, sizeof(struct ListNode));
    node->val = (int)val;
    node->next = NULL;
    q->last->next = node;
    q->last = node;
}

void * dequeue(struct queue * q)
{
    if(q->dummy->next){
        void * ret = (void *)q->dummy->next->val;
        if(q->last == q->dummy->next)
            q->last = q->dummy;
        q->dummy->next = q->dummy->next->next;


        return ret;
    }else
        return NULL;
}

int queue_size(struct queue *q)
{
    int i = 0;
    struct ListNode * p = q->dummy->next;
    while(p){
        p = p->next;
        i++;
    }
    return i;
}

int** zigzagLevelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
    


    if(root == NULL)
        return NULL;
    struct queue * q = init_queue();
    enqueue(q, (void *)root);
    *columnSizes = calloc(10000, sizeof(int));
    int ** ret = calloc(10000, sizeof(int *));
    *returnSize = 0;

    while(q->dummy->next != NULL){
        
        //save node->val;
        
        int size = queue_size(q);
        printf("size = %d level = %d\n", *returnSize);
        ret[*returnSize] = calloc(size, sizeof(int));
        (*columnSizes)[*returnSize] = size;
        
        for(int i = 0; i < size; i++){
            struct TreeNode* node = (struct TreeNode *)dequeue(q);
            printf("%d  ", node->val);
            if(node->left)
                enqueue(q, (void *)node->left);
            if(node->right)
                enqueue(q, (void *)node->right);
            if(*returnSize%2 == 0)
                ret[*returnSize][i] = node->val;
            else 
                ret[*returnSize][size-i-1] = node->val;
        }
        *returnSize +=1;


    }

    return ret;
}