@TOC

对于前、中、后序遍历，相信是大家学习二叉树首先掌握的内容，对于这里我会采用递归和非递归的写法来展示，这里首先展示递归写法，非递归在后续更新

【LeetCode】144.二叉树的前序遍历

原题传送门

---

题目描述.

思路分析.

• 思路很简单，专门写一个前序遍历的函数，写法也是前序遍历的写法，这里在函数传参的时候加个应用

代码详解.

C++版本

class Solution {
private:
    void preOrder(TreeNode* root, vector<int> &ret)
    {
        if(root == NULL)
            return;
        ret.push_back(root->val);
        preOrder(root->left,ret);
        preOrder(root->right,ret);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;

        preOrder(root,ret);

        return ret;
    }
};

C语言版本（递归算法展开图）

看完C++版本是不是觉得这道题很简单，我再补充一个C语言版本的，我们来玩玩指针✒

//前序遍历
void PreOrder(struct TreeNode* root, int* a, int* pi)
{
    if(!root)   return;
    a[(*pi)++] = root->val;
    PreOrder(root->left,a,pi);
    PreOrder(root->right,a,pi);
}

//求解二叉树大小
int TreeSize(struct TreeNode* root){
    if(!root)   return 0;
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}           
int* preorderTraversal(struct TreeNode* root, int* returnSize){     
                                            //数组大小（输出型参数）
    //1.获取当前二叉树大小
    *returnSize = TreeSize(root);           
    //2.根据二叉树大小动态开辟数组存放遍历序列
    int* a = (int *)malloc(sizeof(int) * (*returnSize));
    //3.封装前序遍历
    int i = 0;
    PreOrder(root,a,&i);

    return a;
}

• 可以看到，对于C语言版本的代码看起来即比较冗余和复杂了，因为C语言不像C++那样有现成的STL库，因此有些东西就需要自己去造轮子了，所以对于二叉树前中后序的非递归写法我也会使用C++来实现，后续补充。。。
• 好，我们来看一下本题的C语言写法，和C++给出的主接口函数不一样的地方是在多了一个【returnSize】的指针，而且返回值也是一个指针，哪有同学问这是啥，其实在C语言的很多代码中有个returnSize是很正常的，因为像LeetCode这种接口型的OJ题它后台内部是有代码写好了会调用你写好的这个接口函数，一般来说他会去获取你这个数组的大小，但是呢这里的返回值是【int*】，也就是一个数组，C语言还可以返回结构体，但是比较麻烦，因此这个【returnSize】其实是外界用来获取你函数中算出来的数组大小的，而且他那里传入的是一个地址，所以在函数内部你可以通过【解引用】的方式来修改这个大小
• 因此首先我们先去写了一个函数获取传进来的根节点所在的这棵树的大小，使用解引用这个指针变量来接受，这样外界就可以轻而易举地获取到你这个大小了。==指针接收地址这一块很重要，后面我们还要讲到==

*returnSize = TreeSize(root);      

• 有了这棵树的大小，我们就需要根据这个大小去开辟出存放二叉树遍历序列的数组了，这里当然是使用malloc来开辟，但是对于C++来看，只需要使用vector这个顺序表就可以了，它会自动扩容的。
• 在开辟出这个数组后，我们就可以去打印出前序遍历的序列了，我这里再说一个错误的示范

void PreOrder(struct TreeNode* root, int* a, int i)
{
    if(!root)   return;
    a[i++] = root->val;
    PreOrder(root->left,a,i);
    PreOrder(root->right,a,i);
}

• 可以看到上面我对于最后一个参数我使用的是指针，这个是用来遍历这个数组的，用来存放数据，但是对于这样的写法却存在一定的问题，我们首先提交看看

• 可以看到，通过是通过了，但是呢却出现了一些小问题，我们通过画算法图来看看

• 可以看到，对于这种结构的树，不会有问题，这就是有些案例可以通过的原因
• 我们再来看看另一种

• 可以看到，对于这种结构的树就会出现问题，从算法图可以看出，因为在这个递归的过程中内部形参i的改变不会影响外部的改变，因此在递归完左子树之后递归右子树i还是原来的那个值，就会造成回退，所以这就是上面题目给出的错误案例中为什么会出现这么大一个==随机值==的原因了
• 因此想要真正通过形参的改变影响实参，我们就需要用到【指针接收地址】的思想，就想下面这样

void PreOrder(struct TreeNode* root, int* a, int* pi)
{
    if(!root)   return;
    a[(*pi)++] = root->val;
    PreOrder(root->left,a,pi);
    PreOrder(root->right,a,pi);
}

• 而且在主函数中还是传入i的地址才行

PreOrder(root,a,&i);

• 这样提交就可以通过全部的测试案例了

【LeetCode】94.二叉树的中序遍历

原题传送门

---

题目描述.

思路分析.

• 中序和前序也是一样，换一下根结点放入数组的时机即可

代码详解.

C++版本

class Solution {
private:
    void InOrder(TreeNode* root, vector<int>& ret)
    {
        if(root == NULL)
            return;
        InOrder(root->left, ret);
        ret.push_back(root->val);
        InOrder(root->right, ret);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;

        InOrder(root,ret);

        return ret;
    }
};

C语言版本

• 一样，给出C语言的代码求解，不做分析，你可理解前序后自己谢谢看

//中序遍历
void InOrder(struct TreeNode* root, int* a, int* pi)
{
    if(!root)   return;

    InOrder(root->left,a,pi);
    a[(*pi)++] = root->val;
    InOrder(root->right,a,pi);
}

//求二叉树大小
int TreeSize(struct TreeNode* root)
{
    if(!root)   return 0;
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int i = 0;
    //1.首先获取二叉树大小
    *returnSize = TreeSize(root);

    //2.动态开辟存放中序遍历的数组
    int* a = (int *)malloc(sizeof(int) * (*returnSize));

    //3.中序遍历
    InOrder(root,a,&i);

    return a;
}

• 下面是运行结果

【LeetCode】145.二叉树的后序遍历

原题传送门

---

题目描述.

思路分析.

• 后序也是一样的套路。在遍历完左右子树后再将根节点加入数组

代码详解.

C++版本

class Solution {
private:
    void PostOrder(TreeNode* root, vector<int>& ret)
    {
        if(root == NULL)
            return;
        PostOrder(root->left, ret);
        PostOrder(root->right, ret);
        ret.push_back(root->val);
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;

        PostOrder(root,ret);

        return ret;
    }
};

C语言版本

• 下面是C语言的代码

//后序遍历
void PostOrder(struct TreeNode* root, int* a, int* pi)
{
    if(!root)   return;

    PostOrder(root->left,a,pi);
    PostOrder(root->right,a,pi);
    a[(*pi)++] = root->val;
}

 //求二叉树大小
int TreeSize(struct TreeNode* root)
{
    if(!root)   return 0;
    return TreeSize(root->left) + TreeSize(root->right) + 1;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int i = 0;
    //1.首先获取二叉树大小
    *returnSize = TreeSize(root);

    //2.动态开辟存放中序遍历的数组
    int* a = (int *)malloc(sizeof(int) * (*returnSize));

    //3.中序遍历
    PostOrder(root,a,&i);

    return a;
}

• 下面是运行结果

【LeetCode】102.二叉树的层序遍历

原题传送门

---

题目描述

思路分析

• 对于本题我给出两种解法，也是比较经典的两种思路，一个是DFS【深度优先搜索】以及BFS【广度优先搜索】。
• 对于DFS，需要通过记录遍历的深度，为每一层开辟或新加结点，以达到分割输出每一层结点的效果；
• 对于BFS，需要通过队列来进行辅助，只需在原有的BFS代码模板基础上，加一个size去获取每一层的结点个数即可，到那一层的时候出队对应个数的也可以达到分割输出每一层结点的效果

代码详解

• 给出两种解法，分别是DFS和BFS

DSF——深度优先搜索

class Solution {
private:
    void DFS(TreeNode* cur, vector<vector<int>>& ret, int dep)
    {
        if(cur == NULL) return;
        if(ret.size() <= dep)     //过结果集大小 《= 当前层深度，表明第一层访问本层结点
        {
            vector<int> vec;
            vec.push_back(cur->val);        //创建一个小结果集将其放入
            ret.push_back(vec);
        }
        else
        {
            //若是结果集大小 > 当前层深度，表明已经访问过，直接加入大结果集的当前层小结果集中即可
            ret[dep].push_back(cur->val);        
        }

        //递归其左右子树，开始下一层的访问
        DFS(cur->left, ret, dep + 1);
        DFS(cur->right, ret, dep + 1);      //dep + 1表示深度 + 1
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int dep = 0;
        DFS(root,result,dep);

        return result;
    }
};

• 稍微讲解一下DFS的代码，可能有点难以理解，首先看到是需要三个参数，一个是当前所访问的结点，一个是大的结果集，一个是递归深度，这个在我下面所画的算法图中都有展现出来，接下去说一下存放结果集的过程，主要就是通过大结果集的size()大小和当前递归深度做一个比较，若是<=则表示是第一个次遍历到这一层，表明还没有为这一层开辟一个存放数据的小结果集，就开辟出来然后存入数据，若是【ret.size() > dep】了，那就表明此次访问的还是这一层，只需要将新结点追加在这一层之后即可
• 放入当前结点后便递归其左右子树，当然dep深度也要++，通过这样的逻辑，就可以将一棵树中的所有结点放入一个二维的结果集中
• 以下是我画的算法图解，仅供参考，你可自己去模拟着画画，强调一点，对于递归要多画展开图

BSF——广度优先搜索

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> qu;            //二叉树类型队列
        vector<vector<int>> result;     //存放遍历结点结果集
        if(root != NULL)       qu.push(root);      //存入根结点
        //开始队列操作
        while(!qu.empty())      //直至队列为空
        {
            int sz = qu.size();     //获取当前队列的大小
            vector<int> vec;        //装载每一层的树层结点
            for(int i = 0;i < sz; ++i)
            {
                TreeNode* node = qu.front();        //获取当前队列的队头元素
                qu.pop();       //出队队头元素
                vec.push_back(node->val);

                //子树的入队
                if(node->left)    qu.push(node->left);    //左孩子入队
                if(node->right)    qu.push(node->right);   //右孩子入队
            }
            result.push_back(vec);      //每一层结点放入结果集
        }
        return result;
    }
};

• 然后来说说BFS的具体求解过程

• 上述就是BFS层序遍历的过程，你可试着自己模拟看看

【LeetCode】965.单值二叉树

原题传送门

---

题目描述

思路分析

• 本题的描述很简单，【单值二叉树】就是树中的每一个值都是相等的
• 那我们要怎么去完成这道题目呢？很简单，每次比较其根节点和左右还是是相等即可，若是发现不相等，立马返回false，若是当前相等，则递归其左右子树继续比较，全部比较下来都相等后就访问到空了，便return true

代码详解.

• 下面是代码详解

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;
        /*
          需判断左右孩子是否为空，防止访问空指针
        */
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;   

    //若是根结点与其左右子树均相同，则继续递归其左右子树进行判断
    return isUnivalTree(root->left) && isUnivalTree(root->right);   
}

• 这是它的比较形式

【LeetCode】100.相同的树【⭐】

原题传送门

---

本题对于后面的两题都很有帮助，因此要重点理解

题目描述

思路分析

• 来看看本题的思路，刚才我们在比较一棵树中的结点是否相同，那只需要左右子树进行一个递归即可，但是现在有两棵树了，那该怎么办呢？可以看到，主函数接口中也是给到了两个指向根节点的指针，那其实套路也是一样的，只是需要考虑的情况多了一些

bool isSameTree(struct TreeNode* p, struct TreeNode* q)

• 首先就要考虑的是两棵树是不是都是空树的情况，若都是空树，则表示它们也是相等的
• 其次的话就是要考虑当前传入的两棵树的结点一个空，一个非空的情况，这个条件不可以写在第一个，因为这种情况是包含在两个都非空的情况下的，若是将这个条件写在第一行，那么两棵树进来的当前结点一个空、一个非空就会被【return false】，那就不对了
• 在空和非空判断完了之后就是结点值的判断，这个很直观，不相同返回false即可
• 若是上面的条件均不满足，则表示两棵树到目前为止还是相同的，因此我们去分别递归他们的左右子树即可

代码详解

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //若是两棵均为空树，则表示相同
    if(p == NULL && q == NULL)
        return true;        
    //空与不空的判断要建立在两棵树都非空的情况下
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)        //比较值是否相等
        return false;

    //均判断完成后表示根与左右孩子均一直，递归其左右子树
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);   
}

【LeetCode】101.对称二叉树

原题传送门

---

题目描述

思路分析

• 好，我们来分析一下思路，对于本题的对称二叉树，也叫做【镜像二叉树】，就是你在家里照镜子一下，你动动左手，那镜子中的人动的就是右手；你动动右手，那镜子中的人动的就是左手。那二叉树也是一下，我的左子树对应过来就是你的右子树，你的右子树呢对应过来就是我的左子树。==上面这一段论述你不要以为没有用，可以帮助你理解代码==

代码详解

//不到万不得已不要去破坏原有的结构
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //若是两棵均为空树，则表示相同
    if(p == NULL && q == NULL)
        return true;        
    //空与不空的判断要建立在两棵树都非空的情况下
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)        //比较值是否相等
        return false;

    //均判断完成后表示根与左右孩子均一致，递归其左右子树
    return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);   
}

bool isSymmetric(struct TreeNode* root){
    if(root == NULL)
        return true;
    
    return isSameTree(root->left,root->right);
}

• 可以看到，我复用了上面那题【相同的树】代码，但是仔细看呢，却发现我修改了一些 ，也及时两棵树的左右子树在递归的时候要往不同的子树走，我走左，你走右；我走右，你就走左
• 下面是图示

【LeetCode】226.翻转二叉树

原题传送门

---

因为刚才讲到了镜像二叉树，和本次的翻转二叉树很像，因此将本题也纳入讲解

题目描述

思路分析

• 本题我依旧是给出两个思路，一个是DFS，一个是BFS。
• DFS很简单，很好理解，因为是翻转二叉树，只需要翻转其左右孩子即可，然后接下向下递归，进行翻转；

swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);

• BFS的话和我们上面层序遍历的代码基本一致，只需要在获取到当前结点后交换其左右孩子然后入队即可，后面出队就是翻转后的二叉树

swap(node->left,node->right);

代码详解

DFS

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)    return root;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

• 以下是DFS的翻转过程

BFS

• BFS不做过多讲解吗，核心就在于取到当前队头结点后不要直接将其左右孩子入队，将他们交换一下再入队即可

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> qu;
        if(root == NULL)    return NULL;
        qu.push(root);

        while(!qu.empty())
        {
            int sz = qu.size();
            for(int i = 0;i < sz; ++i)
            {
                TreeNode* node = qu.front();
                qu.pop();
                //此时node已经取到队头结点
                swap(node->left,node->right);
                //继续遍历左右孩子
                if(node->left)      qu.push(node->left);
                if(node->right)     qu.push(node->right);
            }
        }
        return root;
    }
};

【LeetCode】572.另一棵树的子树

原题传送门

---

上一题是一段小插曲，本题也需要使用到No.100的代码，也就是【相同的树】，不过本题稍微难理解一些，所以我会讲得详细一点

题目描述

• 首先来看一下有关题目的描述

思路分析

• 本题的意思就是在一棵树中找另一棵树的子树，那有同学说，这该如何去比较呢？
• 在上面我们学会了如何去比较一棵树中有无相同的结点、两棵树是否相同以及如何去反转一棵树，但是现在的需求是要在一棵树中找到是否包含了另一棵树，存在一个嵌套的逻辑，是会感觉有点烧脑起来了:ocean:
• 于是有的同学就找了各种办法，去左右子树里面递归寻找，一个个翻转控制对比，然后把自己绕晕了，其实这道题只要思路对了，是很好解决的，虽然我们是要找是否存在另一颗子树，但是呢这个过程还是在比较两棵树是否是相同的，因此还是需要用到我们上面写到过的【比较两棵树是否相同】的代码逻辑，就是在主接口中在做一些初始判断即可
• 流程如下
• [x] 判断主树是否为空，若为空则不可能包含子树，因为题目条件给出子树不为空
• [x] 判断两棵树的根是否一致，若是一致表示这是两棵相同的树
• [x] 分别递归其左右子树进行查找对比，复用isSameTree()的代码逻辑

代码详解

//全比一下
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //若是两棵均为空树，则表示相同
    if(p == NULL && q == NULL)
        return true;        
    //空与不空的判断要建立在两棵树都非空的情况下
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)        //比较值是否相等
        return false;

    //均判断完成后表示根与左右孩子均一致，递归其左右子树
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);   
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    //提示中给出子树不可能为空，因此root为空就表示不存在子树
    if(root == NULL)    
        return false;
    //首先比较两棵树的根是否相同
    if(isSameTree(root,subRoot))
        return true;
    //根不同则去递归root的左右子树继续比较
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); 
                                    //使用逻辑或，左子树找到了就无需在往右子树寻找
}

• 这里要说明的一点就是在递归的时候为什么用的是【| |】，而不是【&&】，这就需要你自己思考了，这个符号叫做==按位或==，设想你在左子树中已经找到了包含的子树，那还需要到右子树中去寻找吗？当然是不需要了，按位或的逻辑就是有一个真那整个表达式即为真

递归算法图分解

• 本题还有一些坑，而且代码可能晦涩难懂一些，因为我画一下递归展开图给你看看，你也可以尝试自己画画
• 首先是对于正常的情况

• 然后是需要注意的情况，可以看到在两棵树中只要哪棵树哪里多出来一个结点，那这两棵树就是不同的，对于DFS来说它会一直递归，直至遍历完所有的树为止
• 还是一样的缩略图，截不了清晰的图片:dog:

【NowCoder】KY11.二叉树遍历

原题传送门

---

本题是从【牛客】摘录过来的，也是比较经典的一道题目
对于牛客来说，和力扣不一样的地方在于它是==IO型OJ==，而力扣则是==接口型OJ==，对于IO型的OJ呢我们需要和在VS里面一样，头文件、main函数均需要自己添加，也就是输入输出都由自己来完成；但是对于接口型OJ你只需实现题目给出的这一部分功能即可，但是相对许多公司的面试来说，大多都会采用【牛客】这个平台来进行面试，所以大家在熟悉了力扣之后，对于牛客也要多熟悉熟悉

题目描述

思路分析

• 本题的意思是这样的，你需要输入一些先序遍历后的二叉树序列，字母表示结点值，#表示空树，然后你要根据这个先序序列去构造一棵二叉树，然后再输出其中序遍历后的结果

先序序列转二叉树视频教学

• 但是要怎么去将给出的这一个先序序列构造成一棵二叉树呢，因为这不好用文字讲解，因此我将给出视频做讲解:tv:

[video(video-tDMBwVAP-1671257824075)(type-csdn)(url-https://live.csdn.net/v/embed/263752)(image-https://video-community.csdnimg.cn/vod-84deb4/7d0eb7707dc171ed80610764a0ec0102/snapshots/49b388393aac43ecb511aa325b1e9d6f-00005.jpg?auth_key=4824850606-0-0-eb5ecda7ae7410a9386147ed4a8810e9)(title-先序遍历构造树)]
——【微信手机端看不到】

---

看了视频讲解之后，相信你对先序遍历如何去进行构造应该有了一定的了解，接下去我们将这个思路转化为代码的形式

• 首先第一步，我们要将这个重构的过程封装成一个函数，因为我们肯定要去进行递归，先给出需要传入的参数，说明一下这里为什么要一个指针来接受，而且在主函数中我传入了一个变量的地址，这个变量是用来遍历这个二叉树的先序序列的，这和我们上面在说C语言版本的先序遍历是一个道理，若是在递归的过程中使用的仅仅是普通的变量，虽然递归进去这个i是发生了变化，但是呢在递归回调的时候，却又回到了首次递归进去的那个值，因此在递归右子树时就会出问题，所以这里我们要使用【指针来接受这个变量的地址】，==这样每次递归进去内部的修改就可以带动外部的这个值的修改了==

BTNode* reBuildTree(char* str, int *pi)

• 一开始首先就是要判断一下传进来的字符是否为【#】，若是则表示其为一棵空树，我们单独做处理，返回NULL即可，但是不要忘了将这个遍历先序序列数组的指针后移，便于下一次的访问
• 接下去就是正常的情况，因为我们需要构建出一棵树，树的每一个结点值是需要一棵空间才存放的，而不仅仅是一个char值罢了，因此我们在上面也需要封装一个树结点的结构体，在遇到字母的时候就开辟出一块空间去存放这个结点值，然后继续去递归其左右子树即可，直到碰到【#】就会return递归右子树了

    //若有值，则创建结点存放
    BTNode* node = (BTNode *)malloc(sizeof(BTNode));
    node->data = str[(*pi)++];      //赋值后指向字符序列下一个字符
    
    //递归当前结点的左右子树
    node->lchild = reBuildTree(str,pi);
    node->rchild = reBuildTree(str,pi);

• 然后有关中序序列的遍历很简单，就是普通的递归，便不做说明

代码详解

• 下面是整体的代码展示

#include <stdio.h>
#include <stdlib.h>

typedef struct BinaryTreeNode{
    char data;
    struct BinaryTreeNode* lchild;
    struct BinaryTreeNode* rchild;
}BTNode;

                                //指针接收地址
BTNode* reBuildTree(char* str, int *pi)
{
    if(str[*pi] == '#')
    {           //#表示空树
        (*pi)++;
        return NULL;
    }
    
    //若有值，则创建结点存放
    BTNode* node = (BTNode *)malloc(sizeof(BTNode));
    node->data = str[(*pi)++];      //赋值后指向字符序列下一个字符
    
    //递归当前结点的左右子树
    node->lchild = reBuildTree(str,pi);
    node->rchild = reBuildTree(str,pi);

    return node;
}

void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->lchild);
    printf("%c ",root->data);
    InOrder(root->rchild);
}

int main() {
    int i = 0;
    char str[100];
    scanf("%s",str);

    BTNode* reTree = reBuildTree(str,&i);
    InOrder(reTree);

    return 0;
}

持续更新中，不断汇总二叉树面试题📰📰📰📰📰

---

DFS与BFS万能模板【❗❗❗】

• 可以看到，在二叉树面试题的求解过程中，我大量使用到了两种搜索算法【DFS】和【BFS】，这也是两个非常常用的算法，因此我将给出它们的万能模板，之后遇到题目只需要根据题意进行一些改动即可

==DFS==

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

==BFS==

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};