103 锯齿状层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

C语言要处理和考虑的问题的确太多了..突然想念C++的好.....

思路上: 相比于普通的层次遍历, 要记录每一层遍历的顺序(正序还是逆序)

细节上: 使用二级指针而不是链表记录遍历队列, 更方便.
**returnColumnSizes是一个指向一位数组的指针, 应该初始化后, 代表每一行的实际大小

双层循环: 外层循环记录队列是否为空,
内层循环处理每一层, 记录本层要处理的元素, 并申请数组空间, 对于奇偶层正序或者逆序存储

int** zigzagLevelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    * returnSize=0;
    if(root==NULL){
        return NULL;
    }
    
    
    *returnColumnSizes=malloc(sizeof(int)*100);
    int **ret=malloc(sizeof(int)*100);
    struct TreeNode**queue=malloc(sizeof(struct TreeNode*)*10000);
    int rear=0,front=0;
    
    
    queue[rear++]= root;
    int level=0;
    
    while(rear!=front){
        int size=rear-front;//得到本层的个数
        (*returnColumnSizes)[level]=size;//对于本层申请的数组大小
        ret[level]=malloc(sizeof(int)*size);
        int i=0;
        
        while(size){    //处理本层的所有, 将子节点加入队列
            struct TreeNode*node=queue[front++];    //逐个取出要处理的元素
            if(level%2==0)              //偶数正着存, 奇数逆序存(ret数组). 但是在queue数组是正常存进去的
                ret[level][i++]=node->val;
            else 
                ret[level][size-1]=node->val;
            
            if(node->left)
                queue[rear++]=node->left;
            if(node->right)
                queue[rear++]=node->right;
            size--;
        }
        level++;
    }
    *returnSize=level;
    return ret;
}