【leetcode】102. 二叉树的层序遍历（C语言+队列）

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

[TOC]

102 层序遍历（较难😥）

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

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

/**
 * 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保存了二叉树每一层的节点值

0.错误思路

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

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

1.数组队列初始化

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

#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.初始化数组

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

*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++一次

   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;不然会执行出错

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