[Algorithm][队列][宽搜BFS][N叉树的层序遍历][二叉树的锯齿形层序遍历][二叉树最大宽度][在每个树行中找最大值]详细讲解

目录

  • 1.N 叉树的层序遍历
    • 1.题目链接
    • 2.算法思路详解
    • 3.代码实现
  • 2.二叉树的锯齿形层序遍历
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 3.二叉树最大宽度
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现
  • 4.在每个树行中找最大值
    • 1.题目链接
    • 2.算法原理详解
    • 3.代码实现


1.N 叉树的层序遍历

1.题目链接

  • N 叉树的层序遍历

2.算法思路详解

  • 思路:层序遍历 + 多加一个变量记录每一层结点的个数

3.代码实现

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 sz = q.size(); // 提取本层元素个数
        vector<int> tmp; // 统计本层元素

        while(sz--)
        {
            Node* node = q.front();
            q.pop();

            tmp.push_back(node->val);

            // 将该结点下一层入队列
            for(auto& child : node->children)
            {
                if(child != nullptr)
                {
                    q.push(child);    
                }
            }
        }

        ret.push_back(tmp);
    }

    return ret;
}

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

1.题目链接

  • 二叉树的锯齿形层序遍历

2.算法原理详解

  • 思路:层序遍历 + 增加标记位来比标记需要逆序的层

3.代码实现

vector<vector<int>> ZigzagLevelOrder(TreeNode* root) 
{
    vector<vector<int>> ret;
    queue<TreeNode*> q;

    if(root == nullptr)
    {
        return ret;
    }

    q.push(root);
    bool rvs = false; // reverse
    while(q.size())
    {
        int sz = q.size(); // 本层元素个数
        vector<int> tmp; // 统计本层元素

        while(sz--)
        {
            TreeNode* node = q.front();
            q.pop();

            tmp.push_back(node->val);

            // 孩子节点入队列
            if(node->left)
            {
                q.push(node->left);    
            }

            if(node->right)
            {
                q.push(node->right);    
            }
        }

        if(rvs)
        {
            reverse(tmp.begin(), tmp.end());
        }
        rvs = !rvs;

        ret.push_back(tmp);
    }

    return ret;
}

3.二叉树最大宽度

1.题目链接

  • 二叉树最大宽度

2.算法原理详解

  • 思路一:用层序遍历硬来

    • 统计每⼀层的最⼤宽度,优先想到的就是利⽤层序遍历,把当前层的结点全部存在队列⾥⾯,利⽤队列的⻓度来计算每⼀层的宽度,统计出最⼤的宽度
    • 但是,由于空节点也是需要计算在内的,因此,可以选择将空节点也存在队列⾥面
    • 这个思路是正常会想到的思路,但是极端情况下,最左边⼀条⻓链,最右边⼀条⻓链,需要存⼏亿个空节点,会超过最⼤内存限制
      请添加图片描述
  • 思路二:用数组存储二叉树的方式,给结点编号 -> vector<pair<TreeNode*, int>>

    • 依旧是利⽤层序遍历,但是这⼀次队列⾥⾯不单单存结点信息,并且还存储当前结点如果在数组中存储所对应的下标
    • 这样计算每⼀层宽度的时候,⽆需考虑空节点,只需将当层结点的左右结点的下标相减再加1即可
      请添加图片描述
  • 细节:如果⼆叉树的层数非常极端,下标有可能溢出,且任何⼀种数据类型都存不下下标的值,但是此点对本题并不构成问题

    • 数据的存储是⼀个环形的结构
    • 题⽬说明,数据的范围在int这个类型的最⼤值的范围之内,因此不会超出⼀圈
    • 因此,如果是求差值的话,⽆需考虑溢出的情况
      • 因为哪怕溢出,差值还是在接受范围内的
    • 为了防止溢出,需要使用unsigned int
      请添加图片描述
  • 如何计算每个结点在树中的下标呢?

    • 根据root下标起点,分为两个情况
      请添加图片描述

3.代码实现

int WidthOfBinaryTree(TreeNode* root) 
{
    vector<pair<TreeNode*, size_t>> q; // 用vector模拟queue
    q.push_back({root, 1});

    size_t ret = 0;        
    while(q.size())
    {
        auto& [x1, y1] = q[0]; // 队头
        auto& [x2, y2] = q.back(); // 队尾

        ret = max(ret, y2 - y1 + 1);

        // 将下一层入队列
        vector<pair<TreeNode*, size_t>> tmp;
        for(auto& [x, y] : q)
        {
            if(x->left)
            {
                tmp.push_back({x->left, 2 * y});
            }

            if(x->right)
            {
                tmp.push_back({x->right, 2 * y + 1});
            }
        }
        q = tmp; // 覆盖原队列,避免了队列的头删
    }

    return ret;
}

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

1.题目链接

  • 在每个树行中找最大值

2.算法原理详解

  • 思路:层序遍历 + 统计每一层的最大值

3.代码实现

vector<int> LargestValues(TreeNode* root) 
{
    if(root == nullptr)
    {
        return {};
    }

    vector<int> ret;
    queue<TreeNode*> q;

    q.push(root);
    while(q.size())
    {
        int sz = q.size(), maxV = INT_MIN;
        while(sz--)
        {
            TreeNode* node = q.front();
            q.pop();

            maxV = max(maxV, node->val);

            // 将下一层入队列
            if(node->left)
            {
                q.push(node->left);
            }

            if(node->right)
            {
                q.push(node->right);
            }
        }

        ret.push_back(maxV);
    }

    return ret;
}

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

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

相关文章

数据结构之链表深度讲解

小伙伴们&#xff0c;大家好呀&#xff0c;上次听我讲完顺序表想必收获不少吧&#xff0c;嘿嘿&#xff0c;这篇文章你也一样可以学到很多&#xff0c;系好安全带&#xff0c;咱们要发车了。 因为有了上一次顺序表的基础&#xff0c;所以这次我们直接进入正题&#xff0c;温馨…

Activiti7 开发快速入门【2024版】

记录开发最核心的部分&#xff0c;理论结合业务实操减少废话&#xff0c;从未接触工作流快速带入开发。假设你是后端的同学学过JAVA和流程图&#xff0c;则可以继续向后看&#xff0c;否则先把基础课程书准备好先翻翻。 为什么要工作流 比起直接使用状态字段&#xff0c;工作…

【 书生·浦语大模型实战营】作业(六):Lagent AgentLego 智能体应用搭建

【 书生浦语大模型实战营】作业&#xff08;六&#xff09;&#xff1a;Lagent & AgentLego 智能体应用搭建 &#x1f389;AI学习星球推荐&#xff1a; GoAI的学习社区 知识星球是一个致力于提供《机器学习 | 深度学习 | CV | NLP | 大模型 | 多模态 | AIGC 》各个最新AI方…

【机器学习】集成方法---Boosting之AdaBoost

一、Boosting的介绍 1.1 集成学习的概念 1.1.1集成学习的定义 集成学习是一种通过组合多个学习器来完成学习任务的机器学习方法。它通过将多个单一模型&#xff08;也称为“基学习器”或“弱学习器”&#xff09;的输出结果进行集成&#xff0c;以获得比单一模型更好的泛化性…

上海计算机学会2021年1月月赛C++丙组T2康托表

题目背景 康托是一名数学家&#xff0c;他证明了一个重要的定理&#xff0c;需要使用一张表&#xff1a; 这个表的规律是&#xff1a; 从上到下&#xff1a;每一行的分子依次增大&#xff1b;从左到右&#xff1a;每一列的分母依次增大。 康托以一种不重复、不遗漏的方式&am…

【深耕 Python】Quantum Computing 量子计算机(1)图像绘制基础

一、绘制静止图像 使用matplotlib库绘制函数图像y sin(pi * x): import math import matplotlib.pyplot as pltx_min -2.0 x_max 2.0N 1000x1 [] y1 []for i in range(N 1):x x_min (x_max - x_min) * i / Ny math.sin(math.pi * x)x1.append(x)y1.append(y)plt.xl…

关于继承~

继承 动物有猫、狗&#xff0c; 猫又分为加菲猫、布偶猫......&#xff1b;狗又有哈士奇、德国牧羊犬...... 我们发现&#xff0c;下一类除了拥有上一类的共性之外&#xff0c;还拥有自己的特性。 于是我们可以利用继承的方式来减少重复的代码 继承的基本语法 class A:p…

二叉树的直径

题目描述&#xff1a;给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。两节点之间路径的 长度 由它们之间边数表示。 示例 1&#xff1a; 输入&#xff1a;root […

在剪映专业版中新增字体的方法

我一开始以为剪映专业版没有繁体字&#xff0c;结果发现有一个现代繁体&#xff0c;如图所示: 但是我已经下载了字体了&#xff0c;不用就可惜了。 点击汉仪粗黑繁&#xff0c;安装。 安装之后&#xff0c;重启电脑&#xff0c;打开剪映&#xff0c;就可以搜索到这个字体了。 这…

每日OJ题_贪心算法二④_力扣2418. 按身高排序

目录 力扣2418. 按身高排序 解析代码 力扣2418. 按身高排序 2418. 按身高排序 难度 简单 给你一个字符串数组 names &#xff0c;和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。 对于每个下标 i&#xff0c;names[i] 和 heights[i] 表示第 i 个…

罗宾斯《管理学》第13版/教材讲解/考研真题视频课程/网课

本课程是罗宾斯《管理学》&#xff08;第13版&#xff09;精讲班&#xff0c;为了帮助参加研究生招生考试指定考研参考书目为罗宾斯《管理学》&#xff08;第13版&#xff09;的考生复习专业课&#xff0c;我们根据教材和名校考研真题的命题规律精心讲解教材章节内容。 序号名…

读天才与算法:人脑与AI的数学思维笔记17_歌曲的创作公式

1. 人为何创作音乐 1.1. 音乐一直具有算法性质&#xff0c;这意味着在所有的艺术形式中&#xff0c;它受到人工智能进步的威胁最大 1.1.1. 音乐也是所有艺术形式中最抽象的一种&#xff0c;它利用结构和模式&#xff0c;而正是这种抽象的性质使它与数学紧密相连 1.1.2. 在这…

查找算法之二分查找

一、算法介绍 二分查找&#xff0c;也称为折半查找&#xff0c;是一种在有序数组中查找特定元素的高效算法。对于包含 n 个元素的有序数组&#xff0c;二分查找的步骤如下&#xff1a; 确定搜索范围&#xff1a;首先&#xff0c;将要查找的元素与数组中间的元素进行比较。如果…

【C++】学习笔记——string_5

文章目录 六、string类7. string类的模拟实现8. string类的模拟实现的完整代码string.h头文件test.c源文件 9. string收尾写时拷贝 未完待续 六、string类 7. string类的模拟实现 我们之前讲了实现 insert &#xff0c;但是那个插入函数仅仅是在 pos 位置插入一个字符而且&am…

13.1 QQ邮箱

1. 邮箱发送 2. 准备工作 3. 整合SpringBoot 3.1 配置 依赖引入 <!-- 邮件服务--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency>application.…

发表博客之:transformer 架构 推理时候运算流程详细讲解,以及变长推理支持,小白都可以看得懂,AI推理工程师必备技能!

文章目录 [发表博客之&#xff1a;transformer 架构 推理时候运算流程详细讲解&#xff0c;以及变长推理支持&#xff0c;小白都可以看得懂&#xff0c;AI推理工程师必备技能&#xff01;](https://cyj666.blog.csdn.net/article/details/138439826)总结一下高性能变长推理 发表…

DevicData-P-XXXXXX勒索病毒有什么特点,如何恢复重要数据?

DevicData-P-XXXXXXXX这种新型勒索病毒有什么特点&#xff1f; DevicData-P-XXXXXXXX勒索病毒的特点主要包括以下几点&#xff1a; 文件加密&#xff1a;该病毒会搜索并加密用户计算机上的重要文件&#xff0c;如文档、图片、视频等&#xff0c;使其无法正常打开。这是通过强…

IoTDB 入门教程 问题篇②——RPC远程连接IoTDB服务器失败

文章目录 一、前文二、发现问题三、分析问题四、检查6667端口是否监听所有IP五、检查ECS云服务器的安全组是否允许六、检查Linux防火墙是否允许 一、前文 IoTDB入门教程——导读 二、发现问题 使用本地IP127.0.0.1可以连接IoTDB服务器使用远程IPxx.xx.xx.xx却连接不到。提示你…

抖音小店怎么运营操作,无货源正确做店方式,新手就看这一篇

大家好&#xff0c;我是电商笨笨熊 当前抖店还能做无货源模式吗&#xff1f; 当然可以。 近两年由于平台对于无货源的打击&#xff0c;很多人开始怀疑&#xff0c;无货源模式在抖店还能行得通吗&#xff1f; 抖店这个项目我们做了四年多的时间&#xff0c;无货源模式也是&a…

双fifo流水线操作——verilog练习与设计

文章目录 一、案例分析二、fifo_ctrl模块设计2.1 波形设计&#xff1a;2.2 代码实现2.2.1 fifo_ctrl2.2.2 顶层文件top_fifo_ctrl&#xff08;rx和tx模块省略&#xff09;2.2.3 仿真文件tb_fifo_ctrl 2.3波形仿真 一、案例分析 案例要求&#xff1a;写一个 fifo 控制器&#x…