leetcode102. 二叉树的层序遍历，附带图解，一文教会你使用BFS

Ciderw

1371人浏览 · 2024-07-18 12:15:55

Ciderw · 2024-07-18 12:15:55 发布

leetcode102. 二叉树的层序遍历

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

示例 1：
在这里插入图片描述
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

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

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

其核心思想是利用队列（queue）这一数据结构来实现广度优先搜索（BFS）。这种算法在处理树和图等数据结构时非常常见，因为它能够逐层地访问节点，从而获得每一层的节点值。如下图所示
在这里插入图片描述

代码逻辑分析

1.定义二叉树节点结构：
首先定义了一个TreeNode结构体，它包含一个整数值val，以及指向其左子节点和右子节点的指针left和right。构造函数提供了三种不同的初始化方式，方便在创建节点时灵活设置其值和子节点。

2.初始化结果容器：
vector<vector> res; 这行代码初始化了一个二维向量，用于存储每一层的节点值。

3.处理空树情况：
if (!root) { return res; } 这行代码检查根节点是否为空。如果是空树，则直接返回空的结果向量。

4.初始化队列：
queue<TreeNode*> q; 定义了一个队列q，用于存储待访问的节点指针。

5.开始层序遍历：
while(!q.empty()) 循环直到队列为空。这个循环保证了每一层的节点都被访问。

6.存储当前层的节点值：
vector temp; 初始化一个临时向量，用于存储当前层的节点值。

7.访问当前层的所有节点：
int size=q.size(); 获取当前队列的大小，即当前层的节点数。
for(int i=0;i<size;i++) 循环遍历当前层的所有节点。
TreeNode * node=q.front(); 获取队列头部的节点。
temp.push_back(node->val); 将节点的值添加到临时向量中。
q.pop(); 从队列中移除当前访问的节点。

8.处理子节点：
if(node->left!=nullptr) q.push(node->left); 如果节点的左子节点不为空，则将其添加到队列中，以便在下一轮循环中访问。
if(node->right!=nullptr) q.push(node->right); 同理，处理右子节点。

9.将当前层的节点值添加到结果中：
res.push_back(temp); 将当前层的节点值向量添加到结果向量中。

代码思想

广度优先搜索（BFS）：通过队列实现BFS，逐层访问二叉树的节点。
队列特性：队列的先进先出（FIFO）特性使得我们可以按照从上到下的顺序访问每一层的节点。
层级存储：通过二维向量存储每一层的节点值，使得结果直观且易于理解。

具体代码如下：

/**
 * 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) {
            return res;
        }
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        vector<int> temp;
        int size=q.size();
        for(int i=0;i<size;i++)
        {
            TreeNode * node=q.front();
            temp.push_back(node->val);
            q.pop();
            if(node->left!=nullptr) q.push(node->left);
            if(node->right!=nullptr) q.push(node->right);
        }
        res.push_back(temp);
    }
    return res;
    }
};