/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.07.28
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 
 *  本题考察操作受限的数据结构：栈和队列的的配合出入，树的偶数层(0开始数)先进先出，奇数层先进后出
 *  但是我的算法思路就是：
 *  每一层用动态数组记录,再判定是否为奇偶--偶数层(0开始)顺序,奇数层就将动态数组逆序
 *  在将每一层的动态数组首地址存入到对应的二维结果数组中(层号直接与数组下标对应)
 *  但是我认为用操作不受限的队列也可以实现，不过我觉得思路不够新奇
 * @param pRoot TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */

#include <stdlib.h>
#include <stdbool.h>

//队列结构体
struct QueueNode 
{
    struct TreeNode* Tree_Node;
    struct QueueNode* next;
};

//队列头尾指针以及队列大小
struct Queue 
{
    struct QueueNode* front;
    struct QueueNode* rear;
    int length;
};


// 创建一个空队列
struct Queue* Queue_create() 
{
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = NULL;
    queue->length = 0;
    return queue;
}

//队列判空
bool QueueIsEmpty(struct Queue* queue)
{
    return (queue->length == 0);
}

// 入队
void Queue_in(struct Queue* queue, struct TreeNode* tree_node) 
{
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->Tree_Node = tree_node;
    newNode->next = NULL;

    if (QueueIsEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->length++;
}

// 出队-先入先出
struct TreeNode* Queue_out(struct Queue* queue) 
{
    if (QueueIsEmpty(queue)) {
        return NULL;
    }

    struct TreeNode* tree_node = queue->front->Tree_Node;
    struct QueueNode* temp = queue->front;

    queue->front = queue->front->next;

    //若出队后为空队
    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    free(temp);
    queue->length--;
    return tree_node;
}

//翻转整数数组
int* ReverseArr(int* arr ,int len) 
{
    int left = 0;         // 左指针，从数组开头开始
    int right = len - 1; // 右指针，从数组末尾开始

    // 交换左右指针指向的元素，并同时向中间移动
    while (left < right) {
        // 交换左右指针指向的元素
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // 移动指针
        left++;
        right--;
    }
    
    return arr;
}

int** Print(struct TreeNode* pRoot, int* returnSize, int** returnColumnSizes ) 
{
    // write code here
    if (pRoot == NULL) 
    {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    struct Queue* queue = Queue_create();

    int** result = (int**)malloc(sizeof(int*));
    *returnSize = 0;
    //本题规模大概最多有20层,所以申请20个空间够用了
    *returnColumnSizes = (int*)calloc(20,sizeof(int));

    int currentLevel = 0;//当前树的层数
    int levelNodes = 0; // 当前层的结点数

    //根节点是第0层,偶数，入队
    Queue_in(queue, pRoot);

    while(!QueueIsEmpty(queue))
    {
        levelNodes = queue->length;
         
        int* resultCurrentleverl = (int*)malloc(levelNodes * sizeof(int));
       
        (*returnColumnSizes)[currentLevel] = levelNodes;

        for (int i = 0; i < levelNodes; i++) 
        {
            struct TreeNode* Cur_node = Queue_out(queue);//出队
            resultCurrentleverl[i] = Cur_node->val;//记录出队元素

            if(Cur_node->left)
            {
                Queue_in(queue,Cur_node->left);//左孩子入队(如果有)
            }
            if(Cur_node->right) 
            {
                Queue_in(queue, Cur_node->right);//右孩子入队(如果有)
            }
            
        }

        //层数+1,并将当前层保存在数组中：
        result = (int**)realloc(result, (currentLevel + 1) * sizeof(int*));

        //奇数层则翻转数组,达到先入后出的效果
        if(currentLevel %2 == 1) 
        {
            resultCurrentleverl = ReverseArr(resultCurrentleverl,  levelNodes);
        }
        //将每一层的动态数组存入结果数组中
        result[currentLevel++] = resultCurrentleverl;
    }

    *returnSize = currentLevel;
    free(queue);
    return result;
}