【102. 二叉树的层序遍历 中等】

题目:

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

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

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

示例 2:
输入:root = [1]
输出:[[1]]

示例 3:
输入:root = []
输出:[]

提示:

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

思路:

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历,动画如下:
在这里插入图片描述


代码:

  1. 方法1:借助队列queue实现迭代遍历
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>  que1;
        if(root != NULL) que1.push(root);
        vector<vector<int>> result;

        while(!que1.empty()){
            int size = que1.size();
            vector<int> vec;
            // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的
            while(size--){	//	一个循环对应一层深度
                TreeNode* node = que1.front();
                que1.pop();
                vec.push_back(node->val);    //  将该层的节点存入该层vector中
                if(node->left) que1.push(node->left);   //  将该层节点的左子节点存入queue中,下次循环取出存入vector
                if(node->right) que1.push(node->right); //  将该层节点的右子节点存入queue中,下次循环取出存入vector
            }
            result.push_back(vec);  //将该层vector存储到result中
        }
        return result;
    }
};
  1. 方法2:递归遍历。递归算法的三要素参考【递归法:144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 简单】
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur == NULL) return;
        //  确保在向 result 添加节点之前,每个深度都有一个对应的向量来存储该层级的节点值,从而避免越界访问和未定义行为。
        if(result.size() == depth) result.push_back(vector<int> ());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

总结:

这份代码也可以作为二叉树层序遍历的模板。


参考:

代码随想录

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

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

相关文章

第四届电气工程与控制科学

重要信息 官网&#xff1a;www.ic2ecs.com 时间&#xff1a;2024年12月27-29日 简介 第四届电气工程与控制科学定于2024年12月27-29日在中国南京召开。主要围绕“电气工程“、”控制科学“、”机械工程“、”自动化”等主题展开&#xff0c;旨在为从电…

监控易在汽车制造行业信息化运维中的应用案例

引言 随着汽车制造行业的数字化转型不断深入&#xff0c;信息化类IT软硬件设备的运行状态监控、故障告警、报表报告以及网络运行状态监控等成为了企业运维管理的关键环节。监控易作为一款全面、高效的信息化运维管理工具&#xff0c;在汽车制造行业中发挥着重要作用。本文将结合…

大模型+安全实践之春天何时到来?

引子:距《在大模型实践旅途中摸了下上帝的脚指头》一文发布近一年,2024年笔者继续全情投入在大模型+安全上,深度参与了一些应用实践,包括安全大模型首次大规模应用在国家级攻防演习、部分项目的POC直到项目落地,也推动了一些场景安全大模型应用从0到3的孵化上市。这一年也…

大小端存储的问题

请你用C语言写一个简单的程序&#xff0c;判断你使用的主机是大端存储还是小端存储 #include <stdio.h> int main(){int x 0x11223344;char *p (char *)&x;if(0x44 *p){printf("小端\n");}else if(0x11 *p){printf("大端\n");}return 0; }

山景BP1048增加AT指令,实现单片机串口控制播放音乐(一)

1、设计目的 山景提供的SDK是蓝牙音箱demo&#xff0c;用户使用ADC按键或者IR遥控器&#xff0c;进行人机交互。然而现实很多场景&#xff0c;需要和单片机通信&#xff0c;不管是ADC按键或者IR接口都不适合和单片机通信。这里设计个AT指令用来和BP1048通信。AT指令如下图所示…

EMC VMAX/DMX 健康检查方法

近期连续遇到2个由于对VMAX存储系统没有做及时的健康检查&#xff0c;出现SPS电池故障没有及时处理&#xff0c;然后同一pair就是同一对的另外一个SPS电池再次出现故障&#xff0c;然后存储系统保护性宕机vault&#xff0c;然后业务系统挂掉的案例。 开始之前&#xff0c;先纠…

51c大模型~合集94

我自己的原文哦~ https://blog.51cto.com/whaosoft/12897659 #D(R,O) Grasp 重塑跨智能体灵巧手抓取&#xff0c;NUS邵林团队提出全新交互式表征&#xff0c;斩获CoRL Workshop最佳机器人论文奖 本文的作者均来自新加坡国立大学 LinS Lab。本文的共同第一作者为上海交通大…

移动魔百盒中的 OpenWrt作为旁路由 安装Tailscale并配置子网路由实现在外面通过家里的局域网ip访问内网设备

移动魔百盒中的 OpenWrt作为旁路由 安装Tailscale并配置子网路由实现在外面通过家里的局域网ip访问内网设备 一、前提条件 确保路由器硬件支持&#xff1a; OpenWrt 路由器需要足够的存储空间和 CPU 性能来运行 Tailscale。确保设备架构支持 Tailscale 二进制文件&#xff0c;例…

Webpack学习笔记(4)

1.缓存 可以通过命中缓存降低网络流量&#xff0c;是网站加站速度更快。 然而在部署新版本时&#xff0c;不更改资源的文件名&#xff0c;浏览器可能认为你没有更新&#xff0c;所以会使用缓存版本。 由于缓存存在&#xff0c;获取新的代码成为问题。 接下来将配置webpack使…

java抽奖系统(八)

9. 抽奖模块 9.1 抽奖设计 抽奖过程是抽奖系统中最重要的核⼼环节&#xff0c;它需要确保公平、透明且⾼效。以下是详细的抽奖过程设计&#xff1a; 对于前端来说&#xff0c;负责控制抽奖的流程&#xff0c;确定中奖的人员 对于后端来说&#xff1a; 接口1&#xff1a;查询完…

VulnHub靶场渗透之:Gigachad

环境搭建 VulnHub是一个丰富的实战靶场集合&#xff0c;里面有许多有趣的实战靶机。 本次靶机介绍&#xff1a;http://www.vulnhub.com/entry/gigachad-1,657/ 下载靶机ova文件&#xff0c;导入虚拟机&#xff0c;启动环境&#xff0c;便可以开始进行靶机实战。 虚拟机无法分…

解决Apache/2.4.39 (Win64) PHP/7.2.18 Server at localhost Port 80问题

配置一下apache里面的配置文件&#xff1a;httpd.conf 和 httpd.vhosts.conf httpd.conf httpd-vhosts.conf 重启服务 展示&#xff1a; 浏览器中中文乱码问题&#xff1a;

.NET重点

B/S C/S什么语言 B/S&#xff1a; 浏览器端&#xff1a;JavaScript&#xff0c;HTML&#xff0c;CSS 服务器端&#xff1a;ASP&#xff08;.NET&#xff09;PHP/JSP 优势&#xff1a;维护方便&#xff0c;易于升级和扩展 劣势&#xff1a;服务器负担沉重 C/S java/.NET/…

Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务间的通讯-消息队列【入门四】

继续上一篇任务创建 【Linux下基于最新稳定版ESP-IDF5.3.2开发esp32s3入门任务间的通讯-信号量【入门三】-CSDN博客】 今天要实现消息队列进行任务的通讯 一、从上一篇信号量通讯demo拷贝一份重命名&#xff0c;还是之前的两个任务&#xff0c;重命名了。 xTaskCreatePinned…

【AI日记】24.12.22 容忍与自由 | 环境因素和个人因素

【AI论文解读】【AI知识点】【AI小项目】【AI战略思考】【AI日记】 工作 内容&#xff1a;看 OpenAi 这周的发布会和其他 AI 新闻&#xff0c;大佬视频时间&#xff1a;3 小时 读书 书名&#xff1a;富兰克林自传时间&#xff1a;1 小时评估&#xff1a;读完&#xff0c;总体…

穷举vs暴搜vs深搜vs回溯vs剪枝系列一>电话号码的字母组合

题目&#xff1a; 解析&#xff1a; 代码&#xff1a; private String[] hash {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};private StringBuffer p…

设计模式 -- 单例模式

设计模式 -- 单例模式 单例模式C++ 实现饿汉式单例模式懒汉式单例模式使用静态局部变量实现懒汉式单例模式(推荐)使用call_once实现懒汉式单例模式(推荐)使用静态全局部变量和指针的方式实现懒汉式单例模式(不推荐)双重检测懒汉式单例模式单例模式 单例模式:确保在整个程…

CH430N 插上电脑无反应

电路图&#xff0c;此处我用的是3.3V供电&#xff0c;现象就是插上USB,电脑没有反应。搜索也搜索不到 抄板请看自己是多少V供电 后来看到也有类似的 换了芯片后就好了。md新板子第一个芯片就是坏的&#xff0c;服了。

重拾设计模式--状态模式

文章目录 状态模式&#xff08;State Pattern&#xff09;概述状态模式UML图作用&#xff1a;状态模式的结构环境&#xff08;Context&#xff09;类&#xff1a;抽象状态&#xff08;State&#xff09;类&#xff1a;具体状态&#xff08;Concrete State&#xff09;类&#x…

【MySQL】深入了解索引背后的内部结构

目录 索引的认识&#xff1a; 作用&#xff1a; 索引的使用&#xff1a; 索引底层的数据结构&#xff1a; 哈希表 AVL树 红黑树 B树&#xff1a; B树&#xff1a; B树搜索&#xff1a; 索引的认识&#xff1a; 索引是数据库中的一个数据结构&#xff0c;用于加速查询…