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

网站前置审批类型百度推广开户电话

news 2025/8/14 3:23:04

网站前置审批类型,百度推广开户电话,软件开发人,成都互联网营销师培训二叉树的层序遍历相当于图论的广度优先搜索，用队列来实现 （二叉树的递归遍历相当于图论的深度优先搜索） 102.二叉树的层序遍历给你二叉树的根节点 root ，返回其节点值的层序遍历。 （即逐层地，从左到右…

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

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

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; // 返回最终结果 }
};