【C语言】数据结构-链式二叉树，详解分治递归和层序遍历

慕雪的小助手正在绞尽脑汁···

慕雪小助手的总结

DeepSeek & LongCat

[TOC]

前言

在之前关于树的学习中，我们接触了二叉树的知识点，以及堆和堆排序的操作。

两个知识点都是超链接，可以点击查看我之前的博客，复习一下这两个知识点哦！

接下来我们要更进一步，学习一下链式二叉树的操作

本篇博客将以知识点讲解+OJ题目验证的方式来展开链式二叉树的内容

1.链式二叉树的基本结构

在学习链式二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。

之前我们提到过，树最优的表示方法是父母孩子表示法。但是对于二叉树这种度固定的树来说，可以直接使用最简单的方法，定义两个指针指向它的左右叶子节点即可

typedef int BTDataType;

typedef struct BTreeNode
{
    BTDataType data;
    struct BTreeNode* left;
    struct BTreeNode* right;
}BTNode;

这里要说明的一件事是：普通树的“增删查改”操作是没有意义的，因为树并不是一个最优的储存结构。所以我们学习链式二叉树的操作时，更多学习的是分治递归思想

2.分治递归思想

什么是分治思想？

举个例子，学校里面需要进行排查，找出本校里面身高最高的人。这时候校长可以去找各个年级的级组长，然后级组长去找各个班主任，班主任让班级里面的小组长统计组员身高数据。

这时候的小组长已经可以返回一个身高最高的值给班主任了，然后再层层上报，校长只需要在最后上报的4个数据中找出一个最高的，即为本校最高的同学

分治策略的思想就是分而治之，即先将一个规模较大的大问题分解成若干个规模较小的小问题，再对这些小问题进行解决，得到的解，在将其组合起来得到最终的解。在上面的例子中，较小的问题就是小组长统计组员身高，并上报。转换成代码语言就是return一个值

更详细的解释可以参考这篇大佬的博客👇

五大常见算法策略之——递归与分治策略

早先学习的递归求斐波那契数就运用了分治的思想👉传送门

int fo2(int a)
{
    if ((a == 1) || (a == 2))
        return 1;
    else
        return (fo2(a - 1) )+( fo2(a- 2));//n-1和n-2项
}

当a=1或者2的时候，就是分治的末端节点，通过return 1开始终止递归

3.前/中/后序遍历

了解了上面所说的分治递归思想后，接下来我们再学习链式二叉树的三种遍历方式

前序遍历：根节点-左子树-右子树
中序遍历：左子树-根节点-右子树
后序遍历：左子树-右子树-根节点

从前序遍历入手，我们来实操一下分治的思想：利用递归，以前序遍历的顺序打印出树中节点的值

假设我们现在创建了一个这样的简单二叉树👇你能想出来前序遍历的打印顺序应该是咋样的吗？

答案是1 2 3 4 5 6

看到这里，你肯定一脸懵逼：啊，咋出来的？

不着急，我们现给打印出来的内容加上它们的末端子树NULL，所以前序遍历的结果是：

1	1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

不卖关子啦，直接下手分析这个遍历结果是怎么出来的！

前面提到了，前序遍历的顺序是：根节点-左子树-右子树

下图能让你更直观地看出来这三种遍历方式的不同

其中前序遍历转换为代码语言就是下面这样

// 二叉树前序遍历 
void BTreePrevOrder(BTNode* root)
{
    if (root == NULL)
    {//为了方便理解，把空节点也打印出来
        printf("NULL ");
        return ;
    }
    printf("%d ", root->data);
    BTreePrevOrder(root->left);
    BTreePrevOrder(root->right);
}

在这之中，遇到根节点是NULL的情况，就是分治的末端情况，递归停止

这样说来恐怕还是不清楚，要彻底弄清，我们必须要通过画递归示意图来解决

图中某个单词打错了，画到一半才发现……请忽略它！😭

如果你能理解上图中前序遍历的思路，那中序遍历和后序遍历的操作就非常简单了！猜猜怎么修改前序的代码呢？

没错，只需要更改一下printf的位置就可以了！

// 二叉树中序遍历
void BTreeInOrder(BTNode* root)
{
    if (root == NULL){
        printf("NULL ");
        return;
    }
    
    BTreeInOrder(root->left);
    printf("%d ", root->data);
    BTreeInOrder(root->right);
}
// 二叉树后序遍历
void BTreePostOrder(BTNode* root)
{
    if (root == NULL){
        printf("NULL ");
        return;
    }

    BTreePostOrder(root->left);
    BTreePostOrder(root->right);
    printf("%d ", root->data);
}

最后打印出来的结果分别是这样的，和上面的示意图完全对应！回到示意图

3.1通过递归遍历计算节点个数

上面的递归，我们打印出了各个节点的值

只需要对其中一个递归的代码进行小修改，将printf改成计数++，就能把它从遍历变成计算二叉树的节点个数

这里我选择指针变量的方式让主函数中能获取计数的结果

// 二叉树节点个数
void BTreeSize(BTNode* root,int* pcount)
{
    if (root == NULL)
        return ;
    
    (*pcount)++;//指针变量，main函数中可调用
    BTreeSize(root->left,pcount);
    BTreeSize(root->right,pcount);
}

你可以使用全局静态变量来进行计数，但是那样的计数会在下一次调用的时候叠加，需要在调用后置0，非常不方便

当然，我贴出来的这个方法也不是最优的，因为它需要创建一个额外的变量count作为参数调用，而不能直接return节点的数量

所以就有了下面这个使用三目操作符? :来进行分治递归，计算节点个数

其中根节点为空是末端情况，返回0
其他情况返回左子树和右子树的节点大小+1（该节点自己）

//进阶方法
int BTreeSize(BTNode* root) {
    return root == NULL ? 0 :
        BTreeSize(root->left)
        + BTreeSize(root->right) + 1;
}

3.2用后续遍历的思想销毁树

当我们不需要用二叉树后，需要将其调用的内存释放

问题就来了，如果你释放了根节点，那要咋找到它的左右子树呢？

所以我们在释放的时候，要用后序遍历的顺序来进行释放，即先销毁左右子树，再向上销毁。这样就能避免找不到子树的问题

// 二叉树销毁
void BTreeDestory(BTNode** root)
{
    if (*root == NULL)
        return;

    //通过后续遍历的思想来摧毁树
    BTreeDestory(&(*root)->left);
    BTreeDestory(&(*root)->right);
    free(*root);
    *root = NULL;//使用二级指针可以直接在函数中置空根节点的指针
}

3.3递归法实现前/中/后序遍历

三道Leetcode OJ题

144. 二叉树的前序遍历

145. 二叉树的后序遍历

94. 二叉树的中序遍历

这里只对前序遍历的题目做出讲解，因为后面两个的思路完全一致，只需稍微更改代码

题目给出一个树，需要你将它以前序遍历的顺序，将各个节点的值保存在一个数组中并返回它

这里的输入用例是“伪代码”，[1,null,2,3]代表1的左子树是NULL，右子树是2；2的左子树是3，右子树是NULL

既然需要用数组来储存，首先我们需要知道这个二叉树一共有几个节点，这样才能方便我们开辟数组

注意：这种接口型题目，数组都必须是动态内存函数malloc开辟的，否则无法正常返回。

然后把前序遍历中的printf改成将值放入arr数组中即可！

// 二叉树节点个数
void BTreeSize(struct TreeNode* root,int* pcount)
{
    if (root == NULL)
        return ;
    
    (*pcount)++;
    BTreeSize(root->left,pcount);
    BTreeSize(root->right,pcount);
}
// 前序遍历代码
void BTreePrevOrder(struct TreeNode* root,int*arr,int* i)
{
    if (root == NULL){
        return ;
    }
    
    arr[(*i)++]=root->val;
    //因为在递归调用中需要多次调用不同的i，所以需要取地址
    BTreePrevOrder(root->left,arr,i);
    BTreePrevOrder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int count=0;
    BTreeSize(root,&count);//计算树节点个数
    int* arr=(int*)malloc(sizeof(int)*count);//开辟数组

    int i=0;//下标
    BTreePrevOrder(root,arr,&i);
    *returnSize=count;
    return arr;
}

中序遍历和后续遍历，只需要修改一些代码的位置

// 中序遍历代码
void BTreePrevOrder(struct TreeNode* root,int*arr,int* i)
{
    if (root == NULL){
        return ;
    }
    
    //因为在递归调用中需要多次调用不同的i，所以需要取地址
    BTreePrevOrder(root->left,arr,i);
    arr[(*i)++]=root->val;
    BTreePrevOrder(root->right,arr,i);
}

// 后序遍历代码
void BTreePrevOrder(struct TreeNode* root,int*arr,int* i)
{
    if (root == NULL){
        return ;
    }
    
    //因为在递归调用中需要多次调用不同的i，所以需要取地址
    BTreePrevOrder(root->left,arr,i);
    BTreePrevOrder(root->right,arr,i);
    arr[(*i)++]=root->val;
}

3.4迭代法实现前/中/后序遍历

面试的时候，如果问到前序/中序/后序遍历，如果用递归方式写出来了，面试官可能还会考察你如何用迭代（循环）的方式来实现。

使用循环的方式来进行遍历，需要用到栈。

前序遍历

前序遍历的顺序是中左右，使用一个栈的思路如下

根节点入栈；
开始循环，出栈顶节点，将栈顶节点的右节点和左节点入栈；
重复上述步骤，直到栈为空；

为什么需要先入右节点？因为栈只能从栈顶取数据，用右左的方式插入，取出来的时候就是左右，符合前序遍历的顺序。

下面用C++来实现相关操作，不再造轮子了。

// 前序遍历
// https://leetcode.cn/problems/binary-tree-preorder-traversal/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }

        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* temp = st.top();
            st.pop();
            retV.push_back(temp->val);
            if(temp->right){
                st.push(temp->right);
            }
            if(temp->left){
                st.push(temp->left);
            }
        }
        return retV;
    }
};

后序遍历

后续遍历的顺序是左右中，前序遍历的顺序是中左右；我们只需要将前序遍历代码里面将插入右侧和左侧的顺序交换（先插入左侧，再插入右侧）可以得到一个中右左序列，将这个序列逆置，就可以得到后序遍历的序列。

// https://leetcode.cn/problems/binary-tree-postorder-traversal/
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }

        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* temp = st.top();
            st.pop();
            retV.push_back(temp->val);
            if(temp->left){
                st.push(temp->left);
            }
            if(temp->right){
                st.push(temp->right);
            }
        }
        reverse(retV.begin(),retV.end());
        return retV;
    }
};

中序遍历

迭代方式实现中序遍历的代码和前序后续不太一样。

一直往左走，每个节点都入栈，直到走到空节点；
将此时的cur指针更新为上一层，将上一层的元素插入返回数组；
cur指针往右走；

以下面的树为例，这个树的中序遍历结果是 1 4 2 5 6。

1
2
3

    5
  4   6
1  2

步骤如下

第一次入栈，栈内数据从顶向下是[1,4,5]；
此时cur会遇到1的左侧（空节点），cur更新为栈顶元素1（1出栈），将1插入返回值数组；
cur往1的右边走，右侧为空，cur更新为栈顶元素4；
将4插入返回值数组，往4的右侧走（4出栈），cur为2；
将2入栈，此时栈内元素是[2,5]，往cur左侧走；
2的左子树为空，cur更新为栈顶元素2（2出栈），将2插入返回值数组，往cur右侧走；
2的右子树为空，cur更新为栈顶元素5（5出栈），将5插入返回值数组，往cur右侧走，cur为6；
将6入栈，cur往左侧走，6的左子树为空，cur更新为栈顶元素6（6出栈），将6插入返回值数组，往cur右侧走；
6的右子树为空，此时cur为空，栈为空，树遍历完毕。

代码如下

// https://leetcode.cn/problems/binary-tree-inorder-traversal/
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> retV;
        if(root == nullptr){
            return retV;
        }

        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty())
        {
            if(cur != nullptr)
            {
                st.push(cur);
                // 往左走
                cur = cur->left;
            }
            else
            {
                // 走到空了，将cur更新为当前节点的父亲
                // 将父亲插入数组，再往右边走
                cur = st.top();
                st.pop();
                retV.push_back(cur->val);
                // 往右边走
                cur = cur->right;
            }
        }   
        return retV;
    }
};

使用上面的遍历方式，中序遍历和前序/后序的代码结构不一样。在《代码随想录》中，提供了一个统一方式的迭代写法，可以参考。不过我个人觉得上述这三种比较好理解和记忆，掌握它们已经够了。

4.计算节点个数

在3.1中已经讲述了计算二叉树节点个数的方法，下面是更细致的节点个数计算

4.1叶子节点个数

众所周知，在这颗二叉树中，只有3、5和6是叶子节点

想要判断一个节点是不是叶子节点，其实非常简单：只要它的左右子树都是空，就是叶子节点了。

以此作为分治的末端条件，只要满足这个条件，就返回1
如果已经遍历到空节点了，返回0
其他情况，返回左子树和右子树的叶子节点个数之和

// 二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;

    if (root->left == NULL && root->right == NULL)
        return 1;

    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

4.2二叉树第k层节点个数

假设根节点是第1层，要想知道第k层一共有几个节点，需要怎么设计函数呢？

先来这么想：3所在层数对于根来说是第三层，但是对于2来说是第二层，对于3自己来说是第1层

那么，我们是不是可以让第k层往下-1来进行递归呢？

// 二叉树第k层节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
    assert(k >= 1);//保证k>=1

    if (root == NULL)
        return 0;

    if (k == 1)
        return 1;

    return BTreeLevelKSize(root->left,k - 1)
        + BTreeLevelKSize(root->right,k-1);
}

4.3二叉树的深度

在之前树的概念学习中，讲解过树的深度（即树一共有几层）

深度和之前举例的校长统计身高很相似，我们需要找出左右子树中较深的那一个并进行返回。末端的条件，就是节点为空的时候，return 0终止递归

// 二叉树深度，即一共有几层
int BTreeDepth(BTNode* root)
{
    if (root == NULL)
        return 0;

    int left = BTreeDepth(root->left);
    int right = BTreeDepth(root->right);

    return left > right ? left + 1 : right + 1;
}

注意：这里left+1和right+1是为了计算上节点自己

求二叉树深度OJ题

leetcode上有一道oj题就是求二叉树的最大深度，代码复制上，改个名，搞定！

题目链接：104. 二叉树的最大深度

这个OJ题目也可以通过层序遍历的思路实现。

5.查找树中值为x的节点

在二叉树中查找一个值，基本思想就是把它遍历一遍，判断根节点以及左右子树中是否有x值的节点。

具体的解析，写道下面的代码注释里啦！

// 二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;//节点为空返回空

    if (root->data == x)
        return root;//节点自己就是x，返回节点自己的地址

    BTNode* ret1 = BTreeFind(root->left, x);
    if (ret1 != NULL)//如果左边找到了，返回左节点的地址
        return ret1;

    BTNode* ret2 = BTreeFind(root->right, x);
    if (ret2 != NULL)//如果右边找到了，返回右节点的地址
        return ret2;

    return NULL;//两个都找不到，它自己也不是，返回空
}

6.层序遍历

如同其名，层序遍历就是一层一层地遍历

比如上面这棵树，层序遍历的结果如下

1	1 2 4 3 NULL 5 6

要想实现层序遍历，我们需要借助之前学习的栈和队列知识里的队列👉传送门。在VS项目里面，导入预先写好的队列的头文件和源文件，再引用它就可以了！

这里就能体现出之前预先typedef类型的作用了：只需要更改最先的数据类型，就可以搞定后面的一切！

而引用头文件的时候，因为我们需要在栈的代码中使用二叉树的定义，所以需要先引用二叉树的头文件，再引用队列的头文件

1 2	#include "Btree.h" #include "Queue.h"

6.1层序遍历思路

搞定这个后，我们再来讲述一下层序遍历的思路。

先插入根节点，然后在根节点出队列的同时，插入它的左右子树的节点

当队列中的值都为NULL时，代表层序遍历完成

所以我们需要入队列的不是节点的值，因为那样无法找到节点的左右子树。入队列的是节点的地址！

// 层序遍历
void BTreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root != NULL){//根节点非空，开始入队列
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* head = QueueFront(&q);//取队头数据
        QueuePop(&q);//出队列

        printf("%d ", head->data);
        if (head->left != NULL)
        {
            QueuePush(&q, head->left);
        }
        if (head->right != NULL)
        {
            QueuePush(&q, head->right);
        }
        //层序遍历不需要递归，可以用循环解决问题
    }

    printf("\n");
    QueueDestory(&q);//防止内存泄漏
    return;
}

遍历的结果如下

1	1 2 4 3 5 6

学会了层序遍历，能解决不少leetcode上的OJ题目，这些都会在另外一篇博客中记录👉点我跳转

6.2判断二叉树是否为完全二叉树

学习了层序遍历后，就可以来判断一个二叉树是否为完全二叉树了！

完全二叉树：前k-1层为满二叉树，最后一层不满，但是从左到右分布

具体的思路是

当队列中的队头为NULL时开始遍历，如果队列中都是NULL，代表是满二叉树
如果有非空节点，就不是满二叉树

// 判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);

    if (root != NULL) {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* head = QueueFront(&q);//取队头数据
        QueuePop(&q);//出队列

        if (head == NULL){
            break;//遇到队列中空节点，退出循环
        }

        QueuePush(&q, head->left);
        QueuePush(&q, head->right);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* head = QueueFront(&q);//取队头数据
        QueuePop(&q);//出队列

        if (head != NULL)
        {
            //printf("不是完全二叉树\n");
            return false;
        }
    }

    QueueDestory(&q);//防止内存泄漏
    return true;
}

6.3层序遍历OJ题目

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

1.错误思路

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

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

2.数组队列初始化

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

#define MAX 2000
if (root == NULL)
    return NULL;

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

3.初始化数组

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

*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开辟数组

4.队列操作思路

思路如下：

先让根节点入队列，tail++；
外层循环判断队列是否非空，如果非空就停止操作；
内层循环进行每一层的入队操作，这样才能得到每一层的节点值和节点个数；
在内层循环中创建ret数组的子数组，单独存放每一层的节点值；
最后将每一层的节点个数赋值给*returnColumnSizes数组，*returnSize++一次；

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

这里有一个小问题，当树为空树时，层级应该是0。因为外层需要通过returnSize这个int*指针指向的地址存放的int值来获取节点数量，所以我们需要在第一行赋值*returnSize = 0，判断到root为空的时候直接返回，不然会执行出错。

完整代码如下

/**
 * 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().
 */
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    #define MAX 2000
    *returnSize = 0; //将二叉树层级初始化为0
    if (root == NULL){
        return NULL;
    }

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

    //存放二叉树的每一层节点的值
    int** ret = (int**)malloc(sizeof(int*) * MAX);
    //开辟一个数组来存放每一层的节点个数
    *returnColumnSizes = (int*)malloc(sizeof(int*) * (MAX / 2));

    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;
}

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

5.C++代码

更新一下C++的代码，因为C++有自己的STL容器，所以代码会更加简洁。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> retV;
        if(root == nullptr){
            return retV;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            vector<int> tempV;
            for(int i = 0;i < size;i++)
            {
                TreeNode* front = que.front();
                que.pop();
                tempV.push_back(front->val);
                if(front->left != nullptr){
                    que.push(front->left);
                }
                if(front->right != nullptr){
                    que.push(front->right);
                }
            }
            retV.push_back(tempV); // 一层结束
        }
        return retV;
    }
};