网站服务器费用明细,苏州企业网站制作多少钱,淘宝推广怎么推,齐齐哈尔做网站公司二叉树的层序遍历相当于图论的广度优先搜索#xff0c;用队列来实现
#xff08;二叉树的递归遍历相当于图论的深度优先搜索#xff09;
102.二叉树的层序遍历
给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 #xff08;即逐层地#xff0c;从左到右…二叉树的层序遍历相当于图论的广度优先搜索用队列来实现
二叉树的递归遍历相当于图论的深度优先搜索
102.二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]
思路解析 层序遍历的核心思想 层序遍历或广度优先搜索BFS是通过逐层访问节点来遍历树。通常利用 队列queue 数据结构完成每次处理一层的所有节点然后将下一层的节点加入队列。 算法步骤 特殊情况处理 如果树为空root nullptr直接返回空的二维数组。初始化队列 创建一个队列 que将根节点 root 入队。逐层遍历 每次记录当前队列的大小size代表当前层的节点数量。遍历这一层的节点依次从队列中取出节点存入当前层的结果数组vec。如果节点有左子节点或右子节点将其加入队列作为下一层要访问的节点。记录结果 将当前层的结果数组 vec 添加到最终结果数组 result 中。重复上述过程直到队列为空。返回结果 最终返回存储每一层节点值的二维数组 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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint result; // 用于存储最终的层序遍历结果if (root nullptr) return result; // 如果根节点为空返回空的结果queueTreeNode* que; // 队列用于辅助层序遍历que.push(root); // 将根节点加入队列while (!que.empty()) {int size que.size(); // 当前层的节点数量vectorint 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:vectorint rightSideView(TreeNode* root) {vectorint result; // 用于存储右视图的节点值if (root nullptr) return result; // 如果树为空直接返回空的结果queueTreeNode* 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:vectordouble averageOfLevels(TreeNode* root) {vectordouble result; // 用于存储最终的层序遍历结果if (root nullptr) return result; // 如果根节点为空返回空的结果double arg0;queueTreeNode* que; // 队列用于辅助层序遍历que.push(root); // 将根节点加入队列while (!que.empty()) {int size que.size(); // 当前层的节点数量vectorint vec; // 用于存储当前层的节点值for (int i 0; i size; i) {TreeNode* node que.front(); // 取出队首节点que.pop(); // 弹出队首节点argnode-val;// 将左子节点加入队列if (node-left) {que.push(node-left);}// 将右子节点加入队列if (node-right) {que.push(node-right);}}result.push_back(arg/size); // 将当前层的节点值存入结果中arg0;}return result; // 返回最终结果 }
};
429.N叉树的层序遍历(opens new window)515.在每个树行中找最大值(opens new window)116.填充每个节点的下一个右侧节点指针(opens new window)117.填充每个节点的下一个右侧节点指针II(opens new window)104.二叉树的最大深度(opens new window)111.二叉树的最小深度
还有几道题下次再写
