【LeetCode刷题笔记】102. 二叉树的层序遍历

创作不易，本篇文章如果帮助到了你，还请点赞关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
更多算法知识专栏：算法分析🔥
给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在这里插入图片描述
LeetCode题解专栏：【LeetCode刷题笔记】

题目链接

102. 二叉树的层序遍历

一、题目描述

给你二叉树的根节点root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

二、示例

示例 1：
在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：[ [3],[9,20],[15,7] ]

示例 2：

输入：root = [1]
输出：[ [1] ]
示例 3：

输入：root = [ ]
输出：[ ]

三、题目分析

要按照每层向下遍历，就需要知道每层节点的数量（用于控制每次输出几个数据再进入下一层）

与深度遍历不同的是，在左子树遍历时，需要记住当前层的右子树仍未遍历。

难点在于控制左右子树非兄弟节点也按层输出（例如下图中的6、12、15、7需要在同一层输出，而深入9遍历6和12的时候，15和7就不会被遍历到）

问题转化为如何保存同层仍未遍历的节点或者说遍历同层节点时，如何保存同层非兄弟节点的孩子节点

如果说深度遍历的递归借助了栈先进后出的特性，二叉树的层序遍历就需要先进先出的队列：

先将根节点放入队列，再输出队列头（根节点）的数据，再判断根节点是否存在左右子节点，如果存在就将其入队。

这样，从根节点开始，每次遍历1个节点时，同时将其左右孩子节点放入队列，再按照每层数量从队列中取出每层数据，

每次出队时都进行相同的操作，就实现了按层遍历。

在这里插入图片描述

四、代码实现（C++）

/**
 * 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>> res;	//返回结果：二维数组
        if(root==nullptr)return res;
        queue<TreeNode*> qe;		//打印队列
        qe.push(root);				//将根节点入队
        while(!qe.empty())			//是否还有节点未处理
        {
            vector<int> level;		//每层的打印结果
            int size = qe.size();	//每层节点数量
            for(int i=0;i<size;i++)
            {
                TreeNode* cur = qe.front();			//获取队列头
                level.push_back(cur->val);			//打印节点数据
                if(cur->left)qe.push(cur->left);	//左孩子入队
                if(cur->right)qe.push(cur->right);	//右孩子入队
                qe.pop();			//弹出
            }
            res.push_back(level);	//将每层结果放入二维数组结果中
        }
        return res;
    }
};