TOP101题解 | BM26#求二叉树的层序遍历#

/**
 * 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 层序遍历就要用到队列先进先出的特性了,队列的结构就直接写出\入队，
 *        其余的就是队列元素操作上的一些小细节:主要就是malloc申请的空间大小的扩展和的指向
 * @param root TreeNode类
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */

//队列结构体
#include <stdio.h>
#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;
}

// 入队
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 (queue->length == 0) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->length++;
}

// 出队
struct TreeNode* Queue_out(struct Queue* queue) {
    if (queue->length == 0) {
        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** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }

    struct Queue* queue = Queue_create();
    Queue_in(queue, root);

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

    int currentLevel = 0;
    int levelNodes = 1; // 当前层节点数

    while (queue->length != 0) {
        levelNodes = queue->length;

        // 创建一个动态数组来保存当前层的节点值
        int* currentLevelNodes = (int*)malloc(levelNodes * sizeof(int));

        for (int i = 0; i < levelNodes; i++) {
            struct TreeNode* node = Queue_out(queue);

            currentLevelNodes[i] = node->val;

            if (node->left) {
                Queue_in(queue, node->left);
            }
            if (node->right) {
                Queue_in(queue, node->right);
            }
        }

        // 将当前层的动态数组保存到result中
        result = (int**)realloc(result, (currentLevel + 1) * sizeof(int*));
        result[currentLevel] = currentLevelNodes;

        // 更新当前层节点数和返回数组列数
        (*returnColumnSizes)[currentLevel] = levelNodes;

        currentLevel++;
        (*returnSize)++;
    }

    free(queue);
    return result;
}