TOP101题解 | BM27#按之字形顺序打印二叉树#
按之字形顺序打印二叉树
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
/** * 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; }#TOP101#
TOP101-BM系列 文章被收录于专栏
系列的题解