二叉树层序遍历算法：BFS 思路与 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>> levelOrderBottom(TreeNode* root) {
        
    }
};

题目来源：LeetCode 107. 二叉树的层序遍历 II

核心定义

二叉树的层序遍历，又称广度优先遍历（BFS），是指从根节点开始，按'从上到下、从左到右'的顺序逐层访问树中所有节点，先遍历完第 1 层（根节点），再遍历第 2 层，以此类推，直到最后一层的所有节点都被访问。

实现核心及思路

二叉树层序遍历的本质就是 '先进先出' 的访问逻辑，队列是实现该逻辑的关键数据结构。

大概思路：我们可以将二叉树的节点的地址存入队列，同时，用一个 level_k_size 来记录每一层的节点个数，和一个数组 v 来存储每一层数据，然后利用 level_k_size-- 来控制节点出队列的个数，保证每一层的节点都能够出尽。在节点出队列的同时将节点的 val 值插入数组 v 并将该节点不为空的孩子节点继续带入队列；这样利用 level_k_size 每循环一次得到一层的数据，直到遍历完整个二叉树。

解题思路

1. 通过题目介绍，我们知道函数最后需要返回 vector<vector<int>> 的二维数组，所以，我们先创建一个二维数组 vv。
2. 判断二叉树是否为空，即根结点 root 是否为 nullptr。若为空则不做处理，最后返回一个空的二维数组 vv；不为空，则将根结点 root 入队列，同时 level_k_size 记录节点个数为 1。
3. 根据 level_k_size 来遍历已经入队列的节点。由于 记录的是对应一层的节点数，就可以，（可以用 创建数组），然后，，同时，。