当前位置：首页 > news >正文

二叉树层序遍历 Leetcode102.二叉树的层序遍历

news 2025/7/8 3:14:16

二叉树的层序遍历相当于图论的广度优先搜索，用队列来实现

（二叉树的递归遍历相当于图论的深度优先搜索）

102.二叉树的层序遍历

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

示例 1：

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

思路解析

层序遍历的核心思想
- 层序遍历（或广度优先搜索，BFS）是通过逐层访问节点来遍历树。
- 通常利用 队列（queue） 数据结构完成，每次处理一层的所有节点，然后将下一层的节点加入队列。
算法步骤
1. 特殊情况处理：
  - 如果树为空（root == nullptr），直接返回空的二维数组。
2. 初始化队列：
  - 创建一个队列 que，将根节点 root 入队。
3. 逐层遍历：
  - 每次记录当前队列的大小（size），代表当前层的节点数量。
  - 遍历这一层的节点，依次从队列中取出节点，存入当前层的结果数组（vec）。
  - 如果节点有左子节点或右子节点，将其加入队列，作为下一层要访问的节点。
4. 记录结果：
  - 将当前层的结果数组 vec 添加到最终结果数组 result 中。
5. 重复上述过程，直到队列为空。
6. 返回结果：
  - 最终返回存储每一层节点值的二维数组 result。

que 是一个存储 TreeNode* 类型的队列

/*** 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) {}* };*/
#include <vector>
#include <queue>
using namespace std;class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result; // 用于存储最终的层序遍历结果if (root == nullptr) return result; // 如果根节点为空，返回空的结果queue<TreeNode*> que; // 队列用于辅助层序遍历que.push(root); // 将根节点加入队列while (!que.empty()) {int size = que.size(); // 当前层的节点数量vector<int> vec; // 用于存储当前层的节点值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; // 返回最终结果}
};

107.二叉树的层序遍历||

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

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

思路：我们可以先进行标准的层序遍历，然后将结果逆序。

只需在return result前多加一个 reverse(result.begin(), result.end());

199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

思路：就是其他的元素都不存入，只存入一行中最右边的那个元素

 if (i == size - 1) {result.push_back(node->val);}

所以最后的result就不是二维数组，而是一维数组来存入元素

#include <vector>
#include <queue>
using namespace std;class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> result; // 用于存储右视图的节点值if (root == nullptr) return result; // 如果树为空，直接返回空的结果queue<TreeNode*> que; // 队列用于辅助层序遍历que.push(root); // 根节点入队while (!que.empty()) {int size = que.size(); // 当前层的节点数量for (int i = 0; i < size; i++) {TreeNode* node = que.front(); // 获取队首节点que.pop(); // 弹出队首节点// 如果是当前层的最后一个节点，存入结果if (i == size - 1) {result.push_back(node->val);}// 左子节点入队if (node->left) {que.push(node->left);}// 右子节点入队if (node->right) {que.push(node->right);}}}return result; // 返回右视图结果}
};

637.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

只需要增加计算每层平均数的功能即可

/*** 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<double> averageOfLevels(TreeNode* root) {vector<double> result; // 用于存储最终的层序遍历结果if (root == nullptr) return result; // 如果根节点为空，返回空的结果double arg=0;queue<TreeNode*> que; // 队列用于辅助层序遍历que.push(root); // 将根节点加入队列while (!que.empty()) {int size = que.size(); // 当前层的节点数量vector<int> vec; // 用于存储当前层的节点值for (int i = 0; i < size; i++) {TreeNode* node = que.front(); // 取出队首节点que.pop(); // 弹出队首节点arg+=node->val;// 将左子节点加入队列if (node->left) {que.push(node->left);}// 将右子节点加入队列if (node->right) {que.push(node->right);}}result.push_back(arg/size); // 将当前层的节点值存入结果中arg=0;}return result; // 返回最终结果 }
};