【leetcode】102. 二叉树的层序遍历(C语言+队列)
慕雪年华

这道二叉树的题目相对来说毕竟难,所以又单独拿出来发一篇题解

[TOC]

102 层序遍历(较难😥)

leetcode:102. 二叉树的层序遍历

image

这道题相对来说就么有那么容易了,你可能和我一样,压根没看明白题目要求中的后两个参数是用来干嘛的

image

1
2
3
4
5
6
7
8
/**
* 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:存放的是二叉树的层数
  • **returnColumnSizes:存放的是二叉树每一层的节点个数
  • 返回值要求是int**:需要返回一个指针数组,该数组中的每一个元素是一个数组A,数组A保存了二叉树每一层的节点值

image

0.错误思路

最开始我的想法是,用单独的函数计算出树的节点个数和层级,再进行一次层序遍历来得到树的值。

但很显然,这一思路在本题是搞不通的!🤔

1.数组队列初始化

链式二叉树博客中,我讲述了利用队列来实现层序遍历的思路。这道OJ题目我们也是这么干的。不同的是,在我自己写的队列实现里,使用的是链式队列。而本题使用数组队列会好一点!

1
2
3
4
5
6
7
#define MAX 2000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
if (root == NULL)
return;

struct TreeNode* Queue[MAX];//队列,存放节点的地址
int front = 0, tail = 0;//指向队头和队尾

2.初始化数组

这部分会毕竟绕,先一步一步来理解

1
2
3
4
5
*returnSize = 0;//将二叉树层级初始化为0
//存放二叉树的每一层节点的值
int** ret = (int**)malloc(sizeof(int*) * MAX);
//开辟一个数组来存放每一层的节点个数
*returnColumnSizes = (int*)malloc(sizeof(int*) * (MAX / 2));
  • ret是一个指针数组,存放的是数组A,数组A里面是每一层的节点值。ret也就是题目要求的返回值
  • *returnColumnSizes开辟一个数组来保存每一层的节点数

这里其实returnColumnSizes没有啥二级指针的必要,但是既然题目给了是int**,我们就需要先*解引用再malloc开辟数组

3.队列操作思路

  • 先让根节点入队列,tail++
  • 外层循环判断队列是否非空,如果非空就停止操作
  • 内层循环进行每一层的入队操作,这样才能得到每一层的节点值和节点个数
  • 在内层循环中创建ret数组的子数组,单独存放每一层的节点值
  • 最后将每一层的节点个数赋值给*returnColumnSizes数组,*returnSize++一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   struct TreeNode* head;
Queue[tail++] = root;//根节点入队
while (front != tail)
{
int Csize = 0;//每一层的节点个数
int end = tail;
//end是每一层最末一个节点的指针。在后续的入队列操作中tail会改变,所以需要保存tail的值
ret[*returnSize] = (int*)malloc(sizeof(int*) * (end - front));
//为每一层开辟一个单独的数组来存放值
while (front < end)
{
head = Queue[front++];
ret[*returnSize][Csize++] = head->val;
//数组赋值,同时每一层的节点个数Csize++
if (head->left != NULL)
Queue[tail++] = head->left;
if (head->right != NULL)
Queue[tail++] = head->right;
}
(*returnColumnSizes)[*returnSize] = Csize;//赋值每一层的节点个数
(*returnSize)++;//层数+1
}
return ret;

外层循环结束后,此时ret数组就是题目要求的结果了,返回ret就可以了!

这里有一个小问题,当树为空树时,层级应该是0。所以我们需要在第一行赋值*returnSize = 0;不然会执行出错

image

这道题的思路是我看过题解之后才搞明白的,所以上面的只是一个思路的复现😭还是太菜了!