二叉树的层序遍历（C++详解）

文章目录

写在前面
解题思路
具体做法

写在前面

本篇文章使用C++实现了二叉树的层序遍历。在实现二叉树层序遍历时，一般情况下，大家可能直接输出遍历结果。然而，在解决在线评测（OJ）问题时，有时要求将每一层的遍历结果存储起来，这可能对很多人来说是个挑战。因此，本文详细介绍了如何遍历二叉树的每一层，并将每层遍历的结果存储在二维数组中。

解题思路

首先我们先来介绍一下什么是二叉树的层序遍历（算法知识点：广度优先搜索BFS）。
二叉树的层序遍历是一种按层次逐级访问树节点的方法。该遍历方式从树的根节点开始，逐层自上而下地遍历每个层次的节点，确保同一层次的节点按照从左到右的顺序被访问。在层序遍历中，我们通常使用队列来辅助实现。遍历过程中，首先将根节点入队，然后迭代地将队头节点出队，并将其左右子节点依次入队，以此类推，直到遍历完所有节点为止。这样，我们可以保证每一层的节点被按顺序访问，从而获得二叉树的层次结构信息。
画个图理解一下：

具体做法

理解完上面普通的二叉树的层序遍历以后，我们来说一下如何遍历二叉树的每一层，并将每层遍历的结果存储在二维数组中。
step 1：首先判断二叉树是否为空，空树没有遍历结果。
step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
step 3：每次进入一层，统计队列中元素的个数。因为每当访问完一层，下一层作为这一层的子节点，一定都加入队列，而再下一层还没有加入，因此此时队列中的元素个数就是这一层的元素个数。
step 4：每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点，依次加入队列排队等待访问。
step 5：访问完这一层的元素后，将这个一维数组加入二维数组中，再访问下一层。
代码如下：

vector<vector<int> > levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        //树为空直接返回
        if (root == nullptr) return ret;
        //辅助队列
        queue<TreeNode*> q;
        int count = 0;//记录每层的元素个数
        int level = 0;//记录遍历到哪一层
        q.push(root);队头元素入队列
        while(!q.empty())
        {
            ret.resize(level+1);
            count = q.size();
            //访问每一层元素
            while (count--)
            {
                TreeNode* top = q.front();
                ret[level].push_back(top->val);
                q.pop();
                //左右孩子不为空时，进队列
                if (top->left) q.push(top->left);
                if (top->right) q.push(top->right);
            }
            level++;
        }
        return ret;
    }