【LeetCode】树的BFS(层序遍历)精选6题

目录

1. N 叉树的层序遍历(中等)

2. 二叉树的锯齿形层序遍历(中等)

3. 二叉树的最大宽度(中等)

4. 在每个树行中找最大值(中等)

5. 找树左下角的值(中等)

6. 二叉树的右视图(中等)


1. N 叉树的层序遍历(中等)

先让根结点root入队,队列中:①

第一层遍历:让①出队,让①的孩子③②④入队,队列中:③②④

第二层遍历:让③②④出队,让③的孩子⑤⑥入队(②④没有孩子),队列中:③②④⑤⑥

第三层遍历:让⑤⑥出队,⑤⑥没孩子。

队列为空,层序遍历结束。

代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,把本层节点的值放到临时数组中,并让本层节点的孩子(即下一层节点)入队。该轮层序遍历完成后,把临时数组添加到答案中。

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        if (root == nullptr)
            return {};

        vector<vector<int>> ans;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            int count = q.size(); // 本层节点的个数
            vector<int> tmp; // 记录本层节点的值
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                Node* cur = q.front();
                q.pop();
                // 把本层节点的值放入临时数组中
                tmp.push_back(cur->val);
                // 本层节点的孩子(下一层节点)入队
                for (auto& child : cur->children)
                {
                    if (child != nullptr)
                    {
                        q.push(child);
                    }
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

2. 二叉树的锯齿形层序遍历(中等)

创建一个变量level表示层数,假设二叉树从第1层开始。level为奇数,正序遍历;level为偶数,逆序遍历。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (root == nullptr)
            return {};

        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        int level = 1;
        while (!q.empty())
        {
            int count = q.size(); // 本层节点的个数
            vector<int> tmp; // 记录本层节点的值
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                TreeNode* cur = q.front();
                q.pop();
                // 把本层节点的值放入临时数组中
                tmp.push_back(cur->val);
                // 本层节点的孩子(下一层节点)入队
                if (cur->left)
                {
                    q.push(cur->left);
                }
                if (cur->right)
                {
                    q.push(cur->right);
                }
            }
            // 如果本层是偶数层,将临时数组反转,再放入答案中
            if (level % 2 == 0)
            {
                reverse(tmp.begin(), tmp.end());
            }
            ans.push_back(tmp);
            level++;
        }
        return ans;
    }
};

3. 二叉树的最大宽度(中等)

利用二叉树的顺序存储方式给二叉树的节点编号,假设根结点编号为1,编号为x的节点的两个孩子的编号分别为2x和2x+1。让节点和编号一起入队,每层宽度 = 队尾编号 - 队头编号 + 1。

代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算本层宽度并更新答案,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,并让本层节点的孩子(即下一层节点)入队。

如果二叉树的层数非常非常非常多时,任何一种数据类型都存不下编号。因为无符号整型溢出时会自动取模,而且题目数据保证答案将会在32位带符号整数范围内,所以用unsigned int存储编号就可以保证答案正确。

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        unsigned int ans = 0;
        queue<pair<TreeNode*, unsigned int>> q;
        q.push({ root,1 });
        while (!q.empty())
        {
            unsigned int width = q.back().second - q.front().second + 1; // 本层宽度
            ans = max(ans, width);
            int count = q.size(); // 本层节点的个数
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                TreeNode* cur = q.front().first;
                unsigned int num = q.front().second; // cur的编号
                q.pop();
                // 本层节点的孩子(下一层节点)入队
                if (cur->left)
                {
                    q.push({ cur->left,2 * num });
                }
                if (cur->right)
                {
                    q.push({ cur->right,2 * num + 1 });
                }
            }
        }
        return ans;
    }
};

4. 在每个树行中找最大值(中等)

层序遍历的过程中找最大值。

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (root == nullptr)
            return {};

        vector<int> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int count = q.size(); // 本层节点的个数
            int tmp = INT_MIN;
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                TreeNode* cur = q.front();
                q.pop();
                // 更新tmp
                tmp = max(tmp, cur->val);
                // 本层节点的孩子(下一层节点)入队
                if (cur->left)
                {
                    q.push(cur->left);
                }
                if (cur->right)
                {
                    q.push(cur->right);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

5. 找树左下角的值(中等)

层序遍历的过程中找最左边的值。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if (root == nullptr)
            return {};

        int ans = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int count = q.size(); // 本层节点的个数
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                TreeNode* cur = q.front();
                q.pop();
                // 如果遍历到本层最左边的节点,更新ans
                if (i == 0)
                {
                    ans = cur->val;
                }
                // 本层节点的孩子(下一层节点)入队
                if (cur->left)
                {
                    q.push(cur->left);
                }
                if (cur->right)
                {
                    q.push(cur->right);
                }
            }
        }
        return ans;
    }
};

6. 二叉树的右视图(中等)

层序遍历的过程中找最右边的值。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr)
            return {};

        vector<int> ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int count = q.size(); // 本层节点的个数
            for (int i = 0; i < count; i++)
            {
                // 本层节点出队
                TreeNode* cur = q.front();
                q.pop();
                // 如果遍历到本层最右边的节点,将值添加到答案
                if (i == count - 1)
                {
                    ans.push_back(cur->val);
                }
                // 本层节点的孩子(下一层节点)入队
                if (cur->left)
                {
                    q.push(cur->left);
                }
                if (cur->right)
                {
                    q.push(cur->right);
                }
            }
        }
        return ans;
    }
};

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

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

相关文章

leetcode(动态规划)53.最大子数组和(C++详细解释)DAY12

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给你一个整数数组 nums &#xff0c;请你找出一个具有最大和的连续子数组&#xff08;子数组最少包含一个元素&#xff09;&#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。 示例 提示 2.解答思…

数论 - 博弈论(Nim游戏)

文章目录 前言一、Nim游戏1.题目描述输入格式输出格式数据范围输入样例&#xff1a;输出样例&#xff1a; 2.算法 二、台阶-Nim游戏1.题目描述输入格式输出格式数据范围输入样例&#xff1a;输出样例&#xff1a; 2.算法 三、集合-Nim游戏1.题目描述输入格式输出格式数据范围输…

vue使用Nprogress进度条功能实现

下图中的这种顶部进度条是非常常见的&#xff0c;在vue项目中有对应的插件&#xff1a;Nprogress。 实现效果&#xff1a; csdn也在使用&#xff1a; 或者这样自己使用 1、安装 NProgress可以通过npm安装。 npm install --save nprogress 注意此处的--save等同于-s,就是将…

echats 时间直方图示例

需求背景 某订单有N个定时任务&#xff0c;每个任务的执行时间已经确定&#xff0c;希望直观的查看该订单的任务执行趋势 查询SQL&#xff1a; select UNIX_TIMESTAMP(DATE_FORMAT(exec_time,%Y-%m-%d %H:%i)) execTime, count(*) from order_detail_task where order_no 2…

【C++】vector模拟实现+迭代器失效

vector模拟实现 成员变量定义默认成员函数构造函数 迭代器范围for、对象类型匹配原则 容量操作sizeemptycapacityreserve成员变量未更新memcpy值拷贝 resize内置类型的构造函数 数据访问frontbackoperator[ ] 数据修改操作push_backpop_backswapclearinsertpos位置未更新无返回…

el-button 选择与非选择按钮批量处理

el-button 选择与非选择按钮批量处理 <el-button v-for"(voyage,i) in data[voyages][nowVoyage]":key"i"class"c-work-bts"type"primary":plain"nowWorkSpace!i"click"chooseWorkSpace(i)"size"small&qu…

C#快速配置NLog日志使用

首先我们需要在Nuget中安装Nlog和Nlog-Schema。 添加配置文件&#xff1a;NLog.config <?xml version"1.0" encoding"utf-8" ?> <nlog xmlns"http://www.nlog-project.org/schemas/NLog.xsd"xmlns:xsi"http://www.w3.org/2001…

CSS弹性布局

CSS弹性布局 一、概念 ​ 弹性盒子是 CSS3 的一种新的布局模式。 ​ CSS3 弹性盒&#xff08; Flexible Box 或 flexbox&#xff09;&#xff0c;是一种当页面需要适应不同的屏幕大小以及设备类型时确保元素拥有恰当的行为的布局方式。 ​ 引入弹性盒布局模型的目的是提供一…

山西电力市场日前价格预测【2024-02-21】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-02-21&#xff09;山西电力市场全天平均日前电价为470.29元/MWh。其中&#xff0c;最高日前电价为654.81元/MWh&#xff0c;预计出现在18:45。最低日前电价为355.63元/MWh&#xff0c;预计…

将Windows的系统日志自动收集并且转发到syslog服务器,百试百灵

将windows的系统日志自动收集并且转发到syslog服务器&#xff0c;百试百灵* **使用*Evtsys工具&#xff0c;他会自动收集windows系统日志&#xff0c;然后发送到syslog服务器&#xff0c;并且不乱码 下载链接&#xff1a;百度云永久链接 链接&#xff1a;https://pan.baidu.co…

D9741——用于也收路像机和笔记本电的等设备上的直流转换器。在便携式的仪器设备上。低电压输入时误操作保护电路, 定时闩锁、短路保护电路等功能

D9741是一块脉宽调制方三用于也收路像机和笔记本电的等设备上的直流转换器。在便携式的仪器设备上。 主要特点: 高精度基准电路 定时门锁、短路保护电路 低电压输入时误操作保护电路 输出基准电压(2.5V 超过工作范围能进行自动校正 封装形式: SOP16 应用: 电视摄像机 笔记本电…

5个顶级开源法学硕士大型语言模型 (LLM)

5个顶级开源法学硕士大型语言模型 (LLM)。 在快速发展的人工智能 (AI) 世界中&#xff0c;大型语言模型 (LLM) 已成为推动创新并重塑我们与技术交互方式的基石。 随着这些模型变得越来越复杂&#xff0c;人们越来越重视对它们的访问的民主化。 尤其是开源模型&#xff0c;在这…

算法面试八股文『 模型详解篇 』

说在前面 这是本系列的第二篇博客&#xff0c;主要是整理了一些经典模型的原理和结构&#xff0c;面试有时候也会问到这些模型的细节&#xff0c;因此都是需要十分熟悉的。光看原理还不够&#xff0c;最好是能用代码试着复现&#xff0c;可以看看李沐老师深度学习的教材&#…

线程池:优化多线程管理的利器

引言 同步和异步想必各位都有了解&#xff0c;同步简单来说就是一件事做完再去做下一件&#xff1b;异步则是不用等一件事做完&#xff0c;就可以去做另一件事&#xff0c;当一件事完成后可以收到对应的通知&#xff1b;异步一般应用于一些耗时较长的操作&#xff0c;比如大型…

量子计算:数据安全难题

当今数字技术面临的最大挑战之一是安全系统和数据。为此&#xff0c;人们设计了复杂的算法来加密数据并通过称为对称加密的框架来保护数据。虽然这已被证明是成功的&#xff0c;但量子计算的进步&#xff08;利用量子力学比传统计算机更快地解决复杂问题&#xff09;可能会彻底…

Flink的单元测试介绍及示例

本文详细的介绍了Flink的单元测试&#xff0c;分为有状态、无状态以及作业的测试&#xff0c;特别是针对无状态的单元测试给出了常见的使用示例。 本文除了maven依赖外&#xff0c;没有其他依赖。 一、Flink测试概述 Apache Flink 同样提供了在测试金字塔的多个级别上测试应用程…

离谱,华为食堂也要搞末位淘汰

华为饭堂 末位淘汰 今天逛职场 App&#xff0c;无意间翻到一篇帖子&#xff1a; 点开图片之前&#xff0c;我还以为只是普通的争霸赛被网友解读为末位淘汰。 点开图片后我却发现 ... 可以看出&#xff0c;是深圳华为的行政部做的海报&#xff0c;里面清晰写到&#xff1a;员工的…

QT-地形3D

QT-地形3D 一、 演示效果二、关键程序三、下载链接 一、 演示效果 二、关键程序 #include "ShaderProgram.h"namespace t3d::core {void ShaderProgram::init() {initializeOpenGLFunctions();loadShaders(); }void ShaderProgram::addShader(const QString &fil…

如何使用Docker搭建YesPlayMusic网易云音乐播放器并发布至公网访问

文章目录 1. 安装Docker2. 本地安装部署YesPlayMusic3. 安装cpolar内网穿透4. 固定YesPlayMusic公网地址 本篇文章讲解如何使用Docker搭建YesPlayMusic网易云音乐播放器&#xff0c;并且结合cpolar内网穿透实现公网访问音乐播放器。 YesPlayMusic是一款优秀的个人音乐播放器&am…

JS逆向进阶篇【去哪儿旅行登录】【中篇-滑动轨迹破解补浏览器环境破参数】

目录&#xff1a; 每篇前言&#xff1a;0、整体分析1、逆向轨迹snapshot&#xff08;1&#xff09;分析&#xff1a;&#xff08;2&#xff09;Python轨迹生成&#xff1a;&#xff08;3&#xff09;AES加密&#xff1a;&#xff08;4&#xff09;轨迹加密&#xff1a;&#xf…