算法笔记（十）——队列＋宽搜

news/2024/10/6 21:57:13 标签: 算法, 笔记, 宽搜, C++

文章目录

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

BFS是图上最基础、最重要的搜索算法之一；
每次都尝试访问同一层的节点如果同一层都访问完了，再访问下一层

BFS基本框架

void bfs(起始点)
{
	将起始点放入队列中;
	标记起点已访问;
	while(队列不为空)
	{
		访问队列中首元素;
		删除队首元素;
		for(队首元素所有相邻点)
		{
			if(该点未被访问过且合法)
				将该点加入队列末尾; 
		}
	}
	宽搜结束; 
}

N 叉数的层序遍历

题目：N 叉数的层序遍历

在这里插入图片描述
思路

  • BFS（宽搜）
  • 创建vector<vector<int>> ret来保存结果；
  • 创建queue<Node*> q来将根节点入队，如果根节点为空则直接返回空的ret
  • 当队列不为空的时候一直循环：
    • 获取当前队列大小
    • 用vector<int> tmp来统计本层节点
    • 出队头元素，保存在tmp中，若其孩子节点非空，则进入队列
    • 每层节点出队后，将其保存在tmp中的节点，push_back进ret

C++代码

/*
// 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 == nullptr) 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();
                q.pop();
                tmp.push_back(t->val);
                for(Node* child : t->children) // 让下一次节点入队
                {
                    if(child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

二叉树的锯齿形层序遍历

题目：二叉树的锯齿形层序遍历

在这里插入图片描述
思路1

  • 和上一题的思路一样，我们先封装一个函数vector<vector<int>> levelOrder(TreeNode *root)正常层序遍历该二叉树，将其结果存储在vector<vector<int>> ret
  • 再对结果ret进行逆序，当为偶数层时，对其结果进行逆序；

C++代码

/**
 * 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)
    {
        vector<vector<int>> ret = levelOrder(root);
        // 偶数层时，对其结果进行逆序
        for (int i = 1; i < ret.size(); i += 2)
            reverse(ret[i].begin(), ret[i].end());
        return ret;
    }

    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<TreeNode* > q;
        q.push(root);

        while (q.size())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; 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);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

思路2
我们也可以添加一个标记位flag，当奇数层时，正常添加到结果数组，偶数层时，逆序后进入结果数组

C++代码

/**
 * 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)
    {
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<TreeNode* > q;
        q.push(root);
        int flag = 0; // 标志层数

        while (q.size())
        {
            flag++;
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; 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;
    }

};

二叉树最大宽度

题目：二叉树最大宽度

在这里插入图片描述

思路
对于数组存储的二叉树，我们知道

  • 父亲节点下标为i（从一开始）。则，
  • 左孩子下标为2 * i
  • 左孩子下标为2 * i + 1

如果二叉树非常不平衡，节点全部在右侧，空节点也进行插入操作去计算的话，空间是远远不够的

  • 我们可以通过计算每层插入节点的头和尾下标差值，并使用vector来模拟队列操作
  • 每次都覆盖前一层，以防超出内存
  • 计算差值，使用无符号整型，避免数据溢出
  • 定义一个队列 vector<pair<TreeNode*, unsigned int>> q；// 数组模拟队列，元素包含一个二叉树节点指针和该节点在完全二叉树中的编号
  • 将根节点和其对应编号 1 放入队列 q中
  • 进入循环，获取当前层数收尾元素，并且更新当前最大宽度
  • 创建一个临时队列tmp来更新q

C++代码

/**
 * 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;
    }
};

在每个树行中找最大值

题目：在每个树行中找最大值

在这里插入图片描述

思路

利用层序遍历，统计每层最大值；

C++代码

/**
 * 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) 
    {
        vector<int> ret;
        if(root == nullptr) return ret;

        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            int n = q.size();
            int _max = INT_MIN;
            for(int i = 0; i < n; i++)
            {
                auto t = q.front();
                q.pop();
                _max = max(_max, t->val);

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

http://www.niftyadmin.cn/n/5692203.html

相关文章

【MySQL报错】---Data truncated for column ‘age‘ at row...

【MySQL报错】---Data truncated for column ‘age‘ at row...

目录 一、前言二、问题分析三、解决办法 一、前言 欢迎大家来到权权的博客~欢迎大家对我的博客进行指导&#xff0c;有什么不对的地方&#xff0c;我会及时改进哦~ 博客主页链接点这里–>&#xff1a;权权的博客主页链接 二、问题分析 问题一修改表结构 XXX 为 not n…
阅读更多...
0-1开发自己的obsidian plugin DAY 8

0-1开发自己的obsidian plugin DAY 8

昨天的pull request遭受了ObsidianReviewBot的修改意见&#xff0c;比较有共性的应该是css&#xff0c;原话是&#xff1a;You should avoid assigning styles via JavaScript or in HTML and instead move all these styles into CSS so that they are more easily adaptable …
阅读更多...
脏读、不可重复读、幻读的解决方法

脏读、不可重复读、幻读的解决方法

上一篇博客提到了脏读、不可重复读、幻读的含义&#xff0c;也知道了是因为什么情况导致出现的这些问题&#xff0c;这篇博客就带大家一起来了解一下他们的解决办法~ 脏读&#xff1a;脏读出现的原因主要是因为一个事务读取了另外一个事务未提交的数据&#xff0c;就可能出现脏…
阅读更多...
二分查找算法——寻找旋转排序数组中的最小值点名

二分查找算法——寻找旋转排序数组中的最小值点名

1.题目解析 题目来源&#xff1a;LCR173.点名——力扣 原名&#xff1a;剑指offer——0~n-1中消失的数字 测试用例 题目来源&#xff1a;153.寻找旋转排序数组中的最小值——力扣 测试用例 2.算法原理 点名 如果要寻找消失的数字&#xff0c;可以判断对应下标的数字是否和下标对…
阅读更多...
Linux驱动开发——新字符设备驱动开发

Linux驱动开发——新字符设备驱动开发

文章目录 1 概述2 新字符设备驱动原理2.1 分配和释放设备号2.2 新字符设备注册方法 3 自动创建设备节点3.1 mdev机制3.2 创建和删除类3.3 创建设备 4 设置文件私有数据5 实验程序编写 系列文章&#xff1a; Linux驱动开发——字符设备驱动开发 Linux驱动开发——LED驱动开发 1 …
阅读更多...
wordpress运行环境 php版本过低提示及解决办法

wordpress运行环境 php版本过低提示及解决办法

如果你的wordpress网站上出现“Your server is running PHP version 5.6.40 but WordPress 6.6.2 requires at least 7.2.24.”&#xff0c;意思是“您的服务器运行的是PHP版本5.6.40&#xff0c;但WordPress 6.6.2至少需要7.2.24版本的”。这说明你wordpress网站运行环境有问题…
阅读更多...
在 ArkTS 网络请求中，重新封装一下 http 模块

在 ArkTS 网络请求中，重新封装一下 http 模块

在ArkTS中&#xff0c;重新封装http模块可以提供一个更简洁、更易于使用的API&#xff0c;同时隐藏底层细节&#xff0c;使开发者能够更专注于业务逻辑。以下是一个简单的示例&#xff0c;展示了如何重新封装鸿蒙系统的kit.NetworkKit中的http模块&#xff1a; // 创建一个新的…
阅读更多...
13：URL输入到页面渲染过程

13：URL输入到页面渲染过程

从URL输入到页面渲染的过程是一个复杂而精细的流程&#xff0c;它涉及多个步骤和多个参与方&#xff08;包括浏览器、DNS服务器、服务器等&#xff09;。以下是这一过程的详细解析&#xff1a; 一、URL解析与DNS查找 URL解析&#xff1a; 当用户在浏览器中输入一个URL并按下回…
阅读更多...
最新文章

Copyright @ 2022~2023