算法沉淀——队列+宽度优先搜索（BFS）（leetcode真题剖析）

在这里插入图片描述

算法沉淀——队列+宽度优先搜索（BFS）

  • 01.N 叉树的层序遍历
  • 02.二叉树的锯齿形层序遍历
  • 03.二叉树最大宽度
  • 04.在每个树行中找最大值

队列 + 宽度优先搜索算法（Queue + BFS）是一种常用于图的遍历的算法，特别适用于求解最短路径或最少步数等问题。该算法通常用于在图中寻找从起点到目标点的最短路径。

基本思想：

  1. 初始化队列： 将起始节点放入队列中。
  2. BFS遍历： 从队列中取出一个节点，遍历与该节点相邻且未访问过的节点，将其加入队列。
  3. 标记已访问： 标记已访问的节点，避免重复访问。
  4. 重复步骤2和3： 直到队列为空。

这个算法适用于无权图的最短路径问题。在搜索的过程中，每一层级的节点都会被依次访问，直到找到目标节点。

具体步骤：

  1. 将起始节点加入队列。
  2. 进行循环直到队列为空： a. 从队列中取出一个节点。 b. 如果该节点是目标节点，返回结果。 c. 否则，将与该节点相邻且未访问过的节点加入队列，并标记为已访问。

这种算法适用于许多场景，例如迷宫问题、游戏中的寻路问题、网络路由算法、树问题等。在这些问题中，它能够有效地找到最短路径或最优解。

01.N 叉树的层序遍历

题目链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：
在这里插入图片描述

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

示例 2：

在这里插入图片描述

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 10^4] 之间

思路

在树的层序遍历中经常要使用到的就是队列和宽度优先搜索算法，这是一道经典的队列和宽度优先搜索算法模板题

  1. 初始化一个空的二维向量 ret 用于存储层次遍历的结果。

  2. 如果根节点 root 为空，直接返回空向量 ret。

  3. 创建一个队列 q 并将根节点入队。

  4. 进入主循环，该循环将处理每一层的节点： a. 获取当前队列的大小，即当前层的节点数。 b. 创建一个临时向量 tmp

    用于存储当前层的节点值。 c. 对于当前层的每个节点：

    • 出队一个节点 t。
    • 将节点值 t->val 存入 tmp。
    • 将该节点的所有子节点入队，如果子节点非空。 d. 将 tmp 存入 ret。

  5. 返回最终的层次遍历结果 ret。

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        queue<Node*> q;
        if(!root) return ret;
        q.push(root);
        while(q.size()){
            int n=q.size();
            vector<int> tmp;
            for(int i=0;i<n;++i){
                Node* t=q.front();
                tmp.push_back(t->val);
                for(Node* x:t->children) if(x) q.push(x);
                q.pop();
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

02.二叉树的锯齿形层序遍历

题目链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

在这里插入图片描述

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

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

思路

这一题我们仔细理解题意，我们不难发现这题和上一题的区别就是，在偶数行时需要逆序，所以我们只要再添加一个偶数列逆序的操作即可，其余同上。

  1. 引入一个标志变量 flag，用于标识当前层次是奇数层还是偶数层。初始化为0。
  2. 初始化一个队列 q 用于层次遍历，以及一个二维向量 ret 用于存储结果。
  3. 如果根节点 root 为空，直接返回空向量 ret。
  4. 将根节点入队。
  5. 进入主循环，该循环处理每一层的节点： a. 获取当前队列的大小，即当前层的节点数，用 s 表示。 b. 递增 flag。 c. 创建一个临时向量 tmp 用于存储当前层的节点值。 d. 对于当前层的每个节点：
    • 出队一个节点 t。
    • 将节点值 t->val 存入 tmp。
    • 如果节点 t 的左子节点非空，将其入队。
    • 如果节点 t 的右子节点非空，将其入队。 e. 如果 flag 为偶数，反转 tmp 中的元素顺序。 f. 将 tmp 存入 ret。
  6. 返回最终的层次遍历结果 ret。

代码

/**
 * 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>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> ret;
        if(!root) return ret;
        q.push(root);
        int flag=0;
        while(q.size()){
            int s=q.size();
            flag++;
            vector<int> tmp;
            for(int i=0;i<s;++i){
                TreeNode* t=q.front();
                tmp.push_back(t->val);
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            if(flag%2==0) reverse(tmp.begin(),tmp.end());
            ret.push_back(tmp);
        }
        return ret;
    }
};

03.二叉树最大宽度

题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

示例 1：
在这里插入图片描述

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。

示例 2：
在这里插入图片描述

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。

示例 3：
在这里插入图片描述

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示：

  • 树中节点的数目范围是 [1, 3000]
  • -100 <= Node.val <= 100

思路

这道题最大的坑点在于如果二叉树极度不平衡，若使用模拟的方式，空节点也进行插入操作去计算的话，空间是远远不够的，所以这里我们不能像前面两题这样操作，我们可以通过计算每层插入节点的头和尾下标差值，并使用vector来模拟队列操作，每次都覆盖前一层，以防超出内存，还有计算差值，我们使用无符号整型，这样我们可以避免数据溢出带来的计算错误的值

  1. 定义一个队列 q，其中每个元素是一个 pair，包含一个二叉树节点指针和该节点在完全二叉树中的编号。
  2. 将根节点和其对应编号 1 放入队列 q 中。
  3. 初始化一个变量 ret 用于存储最大宽度。
  4. 进入主循环，该循环用于遍历二叉树的每一层。 a. 获取当前队列的首尾元素，即队列中最左边和最右边的节点及其编号。 b. 计算当前层的宽度，即 y2 - y1 + 1，其中 y1 是最左边节点的编号，y2 是最右边节点的编号。 c. 更新 ret，取 ret 和当前层宽度的较大值。 d. 创建一个临时队列 tmp。 e. 遍历队列 q 中的每个节点：
    • 如果节点有左子节点，将左子节点及其编号（编号乘以 2）加入 tmp。
    • 如果节点有右子节点，将右子节点及其编号（编号乘以 2 加 1）加入 tmp。 f. 将 tmp 赋值给队列 q。
  5. 返回最终的宽度 ret。

代码

/**
 * 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:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*,unsigned int>> q;
        q.push_back({root,1});
        unsigned int ret=0;

        while(q.size()){
            auto& [x1,y1]=q[0];
            auto& [x2,y2]=q.back();
            ret=max(ret,y2-y1+1);

            vector<pair<TreeNode*,unsigned int>> tmp;
            for(auto& [x,y]:q){
                if(x->left) tmp.push_back({x->left,y*2});
                if(x->right) tmp.push_back({x->right,y*2+1});
            }
            q=tmp;    
        }
        return ret;
    }
};

04.在每个树行中找最大值

题目链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：
在这里插入图片描述

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

  • 二叉树的节点个数的范围是 [0,104]
  • -231 <= Node.val <= 231 - 1

思路

根据前面几个题型，我们不难想到，无非就是在层序遍历的基础上增加一个每层的最大值计算，在之前的基础上增加条件即可。

  1. 定义一个队列 q，其中每个元素是二叉树节点指针。
  2. 将根节点放入队列 q 中。
  3. 初始化一个空的数组 ret，用于存储每一层的最大值。
  4. 进入主循环，该循环用于遍历二叉树的每一层。 a. 初始化一个变量 m 为 INT_MIN，用于记录当前层的最大值。 b. 获取当前队列的大小（即当前层的节点数）。 c. 遍历当前层的每个节点：
    • 弹出队列的首元素，即最左边的节点。
    • 更新 m，取 m 和当前节点值的较大值。
    • 如果节点有左子节点，将左子节点加入队列 q。
    • 如果节点有右子节点，将右子节点加入队列 q。 d. 将 m 添加到数组 ret 中。
  5. 返回最终的数组 ret，其中包含了每一层的最大值。

代码

/**
 * 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<int> largestValues(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> ret;
        if(!root) return ret;
        q.push(root);

        while(q.size()){
            int m=INT_MIN;
            int n=q.size();
            for(int i=0;i<n;++i){
                auto t=q.front();
                q.pop();
                m=max(m,t->val);

                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(m);
        }
        return ret;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/387970.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

文件上传-第三方服务阿里云OSS

文件上传-第三方服务阿里云OSS

JAVA后端实现文件上传,比如图片上床功能,有很多实现方案,可以将图片保存到服务器的硬盘上。也可以建立分布式集群,专门的微服务来存储文件常见的技术比如Minio。对于中小型公司&#xff0c;并且上传文件私密性不高的话可以使用第三方的存储服务&#xff0c;比如阿里云、华为云等…
阅读更多...
【51单片机】一个简单的例子TMOD＆TCON带你永远理解【（不）可位寻址】

【51单片机】一个简单的例子TMOD＆TCON带你永远理解【（不）可位寻址】

前言 大家好吖&#xff0c;欢迎来到 YY 滴单片机系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过单片机的老铁 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的《Linux》专栏YY的《数据…
阅读更多...
【超级干货】ArcGIS_空间连接_工具详解

【超级干货】ArcGIS_空间连接_工具详解

帮助里对空间连接的解释&#xff1a; 根据空间关系将一个要素的属性连接到另一个要素。 目标要素和来自连接要素的被连接属性写入到输出要素类。 如上图所示&#xff0c;关键在于空间关系&#xff0c;只有当两个要素存在空间关系的时候&#xff0c;空间连接才有用武之地。 一…
阅读更多...
网站被劫持了怎么解决

网站被劫持了怎么解决

网站被劫持是一种常见的网络安全问题&#xff0c;它通常表现为用户访问网站时被自动跳转到其他页面&#xff0c;这不仅影响用户体验&#xff0c;还可能对网站带来负面影响。面对这种情况&#xff0c;如何运用高技术手段来有效应对和防范网站劫持&#xff0c;成为了一个迫切需要…
阅读更多...
【Linux学习】线程池

【Linux学习】线程池

目录 23.线程池 23.1 什么是线程池 23.2 为什么需要线程池 23.3 线程池的应用场景 23.4 实现一个简单的线程池 23.4.1 RAII风格信号锁 23.4.2 线程的封装 23.4.3 日志打印 22.4.4 定义队列中存放Task类任务 23.4.5 线程池的实现(懒汉模式) 为什么线程池中需要有互斥锁和条件变…
阅读更多...
MySQL学习记录——구 复合查询

MySQL学习记录——구 复合查询

文章目录 1、基本查询2、多表查询3、自连接4、子查询1、多行子查询2、多列子查询3、from句中的子查询 5、合并查询 1、基本查询 看一些例子&#xff0c;不关心具体内容&#xff0c;只看写法 //查询工资高于500或岗位为MANAGER的雇员, 同时还要满足他们的姓名首字母为大写的J …
阅读更多...
Java图形化界面编程——AWT概论 笔记

Java图形化界面编程——AWT概论 笔记

2.3 Container容器 2.3.1 Container继承体系 Winow是可以独立存在的顶级窗口,默认使用BorderLayout管理其内部组件布局;Panel可以容纳其他组件&#xff0c;但不能独立存在&#xff0c;它必须内嵌其他容器中使用&#xff0c;默认使用FlowLayout管理其内部组件布局&#xff1b;S…
阅读更多...
DOM事件练习1

DOM事件练习1

DOM事件练习1 1. 演示效果 2. 分析思路 用 ul 创建四个 li 列表整个列表的背景是红色的&#xff0c;鼠标悬浮在列表上&#xff0c;一行的变为蓝色点击任意列表&#xff0c;整个列表的背景变为白色&#xff0c;被点击的列表变为粉色需要用到 js 的点击事onclick件和forEach循环…
阅读更多...
【并发编程】ThreadPoolExecutor类

【并发编程】ThreadPoolExecutor类

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;并发编程⛺️稳重求进&#xff0c;晒太阳 ThreadPoolExecutor 1) 线程池状态 ThreadPoolExecutor 使用 int 的高 3 位来表示线程池状态&#xff0c;低 29 位表示线程数量 状态名 高三位 …
阅读更多...
网络安全威胁，如何解决缓冲区溢出攻击

网络安全威胁，如何解决缓冲区溢出攻击

目录 一、什么是网络安全 二、什么是缓冲区 三、缓冲区溢出 四、缓冲区溢出攻击的类型 一、什么是网络安全 网络安全&#xff08;Network Security&#xff09;指的是保护计算机网络及其相关设备、系统和数据免受未经授权访问、破坏、篡改、窃取或滥用的威胁和攻击。随着网…
阅读更多...
【C语言必刷题】1.打印1~100之间的奇数

【C语言必刷题】1.打印1~100之间的奇数

&#x1f4da;博客主页&#xff1a;爱敲代码的小杨. ✨专栏&#xff1a;《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞&#x1f44d;&#x1f3fb;收藏⭐评论✍&#x1f3fb;&#xff0c;您的三连就是我持续更新的动力❤️ &#x1f64f;小杨水平有…
阅读更多...
[职场] 应聘销售的简历怎么写 #职场发展#笔记

[职场] 应聘销售的简历怎么写 #职场发展#笔记

应聘销售的简历怎么写 应聘销售的简历怎么写1 基本信息 姓名&#xff1a;吴x 性别&#xff1a;女 毕业院校&#xff1a;徐州师范大学计算机科学院 学历&#xff1a;大专 联系电话&#xff1a;电子邮件&#xff1a; 工作经验&#xff1a;4年 求职意向 期望从事职业&#xff1a;销…
阅读更多...
前端秘法基础式(HTML)(第二卷)

前端秘法基础式(HTML)(第二卷)

目录 一.表单标签 1.表单域 2.表单控件 2.1input标签 2.2label/select/textarea标签 2.3无语义标签 三.特殊字符 一.表单标签 用来完成与用户的交互,例如登录系统 1.表单域 <form>通过action属性,将用户填写的数据转交给服务器 2.表单控件 2.1input标签 type…
阅读更多...
(03)Hive的相关概念——分区表、分桶表

(03)Hive的相关概念——分区表、分桶表

目录 一、Hive分区表 1.1 分区表的概念 1.2 分区表的创建 1.3 分区表数据加载及查询 1.3.1 静态分区 1.3.2 动态分区 1.4 分区表的本质及使用 1.5 分区表的注意事项 1.6 多重分区表 二、Hive分桶表 2.1 分桶表的概念 2.2 分桶表的创建 2.3 分桶表的数据加载 2.4 …
阅读更多...
UART通信中的奇偶校验

UART通信中的奇偶校验

UART通信中的奇偶校验&#xff1a;提升数据传输可靠性的简单方法 在微控制器&#xff08;MCU&#xff09;和各种电子设备之间的数据通信领域&#xff0c;UART&#xff08;Universal Asynchronous Receiver/Transmitter&#xff0c;通用异步收发传输器&#xff09;协议是一种广泛…
阅读更多...
23款奔驰S400商务版没有后排电动座椅那改装一套跟选装有区别吗

23款奔驰S400商务版没有后排电动座椅那改装一套跟选装有区别吗

改装的后排电动座椅通常提供以下功能&#xff1a; 电动调节&#xff1a;座椅可以通过按钮或控制面板进行前后调节&#xff0c;以适应乘客的腿部空间需求。 靠背角度调节&#xff1a;乘客可以通过电动调节功能来调整座椅的靠背角度&#xff0c;以获得更舒适的坐姿。 座椅倾斜调…
阅读更多...
投资银行在网络安全生态中的作用

投资银行在网络安全生态中的作用

文章目录 一、投资银行的含义（一）并购买方。（二）并购卖方。（三）IPO辅助。（四）投资银行业务的另一方面是帮助这些交易融资。二、从投资银行角度看网络安全产业（一）行业的短期前景三、复杂的网络安全并购（一）行业知识对投资银行业务很重要（二）在网络安全领域，技术…
阅读更多...
嵌入式C语言学习——基于Linux与GCC(二)

嵌入式C语言学习——基于Linux与GCC(二)

系列文章目录 一.C语言常用关键字及运算符操作 文章目录 系列文章目录内存四区指针指针概述指针 修饰符constvoliatiletypedef 指针运算符多级指针 数组数组空间字符空间及地址 结构体、共用体定义、字节对齐位域 内存分布图段错误分析 内存四区 C/C语言的内存四区&#xff…
阅读更多...
MySQL 基础知识（六）之数据查询（一）

MySQL 基础知识（六）之数据查询（一）

目录 1 基本查询 1.1 查询相关列 (select * / 列名) 1.2 别名 (as) 1.3 去重 (distinct) 1.4 对列中的数据进行运算 (、-、*、/) 2 条件查询 (where) 2.1 等值查询 () 2.2 非等值查询 (>、<、>、<、!、><) 2.3 逻辑判断 (and、or、not) 2.4 区间判…
阅读更多...
Shell 学习笔记（一）-Shell脚本编程简介

Shell 学习笔记（一）-Shell脚本编程简介

一 什么是shell&#xff1f; shell是一个用 C 语言编写的程序&#xff0c;它是用户使用 Linux 的桥梁。Shell 既是一种命令语言&#xff0c;又是一种程序设计语言。 Shell 是指一种应用程序&#xff0c;这个应用程序提供了一个界面&#xff0c;用户通过这个界面访问操作系统内…
阅读更多...
最新文章

Copyright @ 2022~2023