
石神
V1
2023/03/08阅读:8主题:全栈蓝
【二叉树】二叉树的层序遍历
二叉树的层序遍历
本文只是节选公众号的中的一篇,我的公众号每日都会更新,欢迎参观 公众号算法每日一更
-
解法一:迭代法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/* 关于本类题的参数:
res是自己要申请的返回值
returnSize 要返回行数,因此是整型指针
returnColumnSizes 要返回(*returnSize)个列数,因此是一维数组的指针
*/
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
*returnSize = 0;
if(root == NULL) return NULL;
int** res = (int**)malloc(sizeof(int*) * 2000);
*returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
struct TreeNode* data[2001];
int front = 0, rear = 0;
struct TreeNode* cur;
data[rear++] = root;
while(front != rear){
int colSize = 0;
int last = rear;
// 申请本层所需列数
res[*returnSize] = (int*)malloc(sizeof(int) * (last - front));
while(front < last){
// 取出本层内容
cur = data[front++];
res[*returnSize][colSize++] = cur -> val;
// 存入下一层内容
if(cur -> left != NULL)
data[rear++] = cur -> left;
if(cur -> right != NULL)
data[rear++] = cur -> right;
}
// 更新行数列数
(*returnColumnSizes)[*returnSize] = colSize;
(*returnSize)++;
}
return res;
}
-
解法二:深度优先(DFS)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
struct Queue{
struct TreeNode* node;
struct Queue* next;
};
// 插入到队尾
void enQueue(struct Queue * queueHead, struct TreeNode* node){
struct Queue* queueIt = queueHead;
while(queueIt -> next != NULL){
queueIt = queueIt -> next;
}
struct Queue* queueNew = malloc(sizeof(struct Queue));
queueNew -> node = node;
queueNew -> next = NULL;
queueIt -> next = queueNew;
}
// 从队头删除
struct TreeNode* deQueue(struct Queue* queueHead){
struct Queue* queueIt = queueHead -> next;
struct TreeNode* node;
if(queueIt != NULL){
queueHead -> next = queueIt -> next;
node = queueIt -> node;
free(queueIt);
return node;
}
return NULL;
}
void freeQueue(struct Queue* queueHead){
// 清理链表
struct Queue* queueIt = queueHead -> next;
struct Queue* queuePre = queueHead -> next;
if(queueIt != NULL){
queuePre = queueIt;
queueIt = queueIt -> next;
free(queuePre);
}
free(queueHead);
}
void bfs(int* returnSize, int** returnColumnSizes, int** res, struct Queue* queueHead){
struct Queue* queueIt = queueHead -> next;
if(queueIt -> node == NULL)
return;
int count = 0;
res[*returnSize] = (int*)malloc(sizeof(int) * 2000);
while(1){
struct TreeNode* node = deQueue(queueHead);
if(node == NULL) break;
// 读队列内容
res[*returnSize][count++] = node -> val;
// 下一层入队
if(node -> left != NULL)
enQueue(queueHead, node -> left);
if(node -> right != NULL)
enQueue(queueHead, node -> right);
}
enQueue(queueHead, NULL);
(*returnColumnSizes)[*returnSize] = count;
*returnSize = *returnSize + 1;
bfs(returnSize, returnColumnSizes, res, queueHead);
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
*returnSize = 0;
if(root == NULL) return NULL;
int** res = (int**)malloc(sizeof(int*) * 2000);
*returnColumnSizes = (int*)malloc(sizeof(int) * 2000);
struct Queue *queueHead = malloc(sizeof(struct Queue));
queueHead -> next = NULL;
queueHead -> node = NULL;
enQueue(queueHead, root);
enQueue(queueHead, NULL);
bfs(returnSize, returnColumnSizes, res, queueHead);
free(queueHead);
return res;
}
明天题就来了
作者介绍

石神
V1