二叉树层序遍历

题目描述

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

假设有这样一棵二叉树,那么它经过层序遍历的结果就应该是:

[[3],[9,20],[15,7]]

解法

我们可以用广度优先搜索解决这个问题。

  • 按层打印: 题目要求的二叉树的 从上至下 打印(即按层打印),又称为二叉树的 广度优先搜索,通常借助 队列 的先入先出特性来实现。
  • 每层打印到一行: 将本层全部节点打印到一行,并将下一层全部节点加入队列,以此类推,即可分为多行打印。

初始化: 打印结果列表 res = [] ,包含根节点的队列 queue = [root] 。


循环: 当队列 queue 为空时跳出。
        新建一个临时列表 tmp ,用于存储当前层打印结果。
        当前层打印循环: 循环次数为当前层节点数(即队列 queue 长度)。
                出队: 队首元素出队,记为 node。
                打印: 将 node.val 添加至 tmp 尾部。
                添加子节点: 若 node 的左(右)子节点不为空,则将左(右)子节点加入队列 queue 
        将当前层结果 tmp 添加入 res 。


返回: 返回打印结果列表 res 即可。

需要注意的是:进行特例处理,当根节点为空,则返回空列表 

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        queue<TreeNode*> q;//设置辅助队列

        vector<vector<int>> res;//用来存储最终结果

        if (root != nullptr) q.push(root);
        while (!q.empty()) {

            vector<int> tmp;//每一层遍历以前都初始化tmp
//这里需注意由于在for循环的执行过程中q.size()的值会进行更改,因此q.size()只能作为i的起点而不是终点
            for(int i = q.size(); i > 0; --i) {
                root = q.front();
                q.pop();
                tmp.push_back(root->val);//在出队列的时刻进行打印,出队列的同时左右结点都入队列
                if (root->left != nullptr) q.push(root->left);
                if (root->right != nullptr) q.push(root->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

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

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

相关文章

css美化滚动条样式

效果展示 实现 滚动条宽&#xff0c;高度 /* 整体滚动条 */ ::-webkit-scrollbar {width: 10px; }/* 滚动条轨道 */ ::-webkit-scrollbar-track {background-color: #ffffff;border-radius: 6px; }/* 滚动条滑块 */ ::-webkit-scrollbar-thumb {background-color: #888;borde…

IDEA安装使用、JDBC

day53续 IDEA安装 浏览器搜索&#xff0c;在idea官网直接下载需要的版本安装包&#xff0c;安装流程基本无脑 对于专业版要激活&#xff0c;可找相关资源也可购买&#xff1b;社区版不需要 配置环境变量 JDBC JDBC:java database connectivity SUN公司提供的一套操作数据库的…

计算机毕业设计Python深度学习美食推荐系统 美食可视化 美食数据分析大屏 美食爬虫 美团爬虫 机器学习 大数据毕业设计 Django Vue.js

Python美食推荐系统开题报告 一、项目背景与意义 随着互联网和移动技术的飞速发展&#xff0c;人们的生活方式发生了巨大变化&#xff0c;尤其是餐饮行业。在线美食平台如雨后春笋般涌现&#xff0c;为用户提供了丰富的美食选择。然而&#xff0c;如何在海量的餐饮信息中快速…

【Excel、RStudio计算T检测的具体操作步骤】

目录 一、基础知识1.1 显著性检验1.2 等方差T检验、异方差T检验1.3 单尾p、双尾p1.3.1 检验目的不同1.3.2 用法不同1.3.3 如何选择 二、Excel2.1 统计分析工具2.1.1 添加统计分析工具2.1.2 数据分析 2.2 公式 -> 插入函数 -> T.TEST 三、RStudio 一、基础知识 参考: 1.…

2.2章节python的变量和常量

在Python中&#xff0c;变量和常量有一些基本的概念和用法&#xff0c;但需要注意的是&#xff0c;Python本身并没有内置的“常量”类型。然而&#xff0c;程序员通常会遵循一种约定&#xff0c;即使用全部大写的变量名来表示常量。 一、变量 在Python中&#xff0c;变量是一…

新手教学系列——【Ubuntu】SSH配置详解

在使用Ubuntu进行远程管理和开发时,SSH(Secure Shell)是必不可少的工具。SSH不仅提供安全的远程登录功能,还支持安全的文件传输和端口转发。然而,有时我们可能会遇到SSH连接中断的问题。本文将详细介绍如何配置SSH以提高其稳定性,并解释关键配置项。 为什么会出现SSH连接…

基于X86+FPGA的精密加工检测设备解决方案

应用场景 随着我国高新技术的发展和国防现代化发展&#xff0c;航空、航天等领域需 要的大型光电子器件&#xff0c;微型电子机械、 光 电信息等领域需要的微型器件&#xff0c;还有一些复杂零件的加工需求日益增加&#xff0c;这些都需要借助精密甚至超精密的加工检测设备 客…

算法 —— 滑动窗口

目录 长度最小的子数组 无重复字符的最长子串 最大连续1的个数 将x减到0的最小操作数 找到字符串中所有字母异位词 长度最小的子数组 sum比target小就进窗口&#xff0c;sum比target大就出窗口&#xff0c;由于数组是正数&#xff0c;所以相加会使sum变大&#xff0c;相减…

实施粘贴式导航_滚动事件

● 所谓的粘贴式导航&#xff0c;就是当我们滑动页面到某一个位置的时候&#xff0c;导航不会因为滑动而消失&#xff0c;会固定在页面的顶部&#xff0c;我们来看一下如何实现&#xff1b; ● 首先我们要获取我们想要滚动到哪一部分的时候让导航栏显示出来&#xff0c;这就需要…

前端工程化09-webpack静态的模块化打包工具(未完结)

9.1、开发模式的进化历史 webpacks是一个非常非常的强大的一个工具&#xff0c;相应的这个东西的学习也是有一定的难度的&#xff0c;里边的东西非常的多&#xff0c;里面涉及到的 概念的话也是非常非常的多的。 这个东西既然非常重要&#xff0c;那么在我们前端到底处于怎样…

填志愿选专业,文科男生如何选专业?

又到了高考分数出炉&#xff0c;无数学子收获喜悦的季节&#xff0c;在分数刚出炉时&#xff0c;很多学生表现的异常兴奋&#xff0c;于他们而言&#xff0c;这么多年的努力终于有了收获&#xff0c;自己该考虑选择什么专业了。而毫不夸张的说&#xff0c;很多人在拿到专业目录…

前程无忧滑块

声明(lianxi a15018601872) 本文章中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;抓包内容、敏感网址、数据接口等均已做脱敏处理&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 前言(lianxi …

使用机器学习,轻松预测问题产品,低成本高效率解决产品质量监测需求

01、案例说明 这个案例是一个酒厂&#xff0c;通过对其产品中不同化学性质的指标数值&#xff0c;寻找哪些是可能出现问题的产品。这是一个标准的离异点&#xff08;Outlier&#xff09;使用情形。 如果能够将在不同属性的一定范围之内的数据&#xff0c;作为判断的标准&#…

JS(JavaScript)的BOM操作

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

C语言实现简单的minishell

探索开源项目&#xff1a;MiniShell 引言 在计算机编程的世界里&#xff0c;Shell 是一个至关重要的组成部分&#xff0c;它允许用户与操作系统交互&#xff0c;执行命令和程序。MiniShell 是一个简化版的 Shell 程序&#xff0c;通常用于教学和学习目的。在本文中&#xff0…

印尼火出圈的本土网盟okspin助力slot游戏广告代投策略

印尼火出圈的本土网盟okspin助力slot游戏广告代投策略 在当今日益全球化的数字营销环境中&#xff0c;本土网盟广告平台在推广特定地区的产品和服务方面发挥着至关重要的作用。特别是在印尼这样的多元文化市场中&#xff0c;本土网盟okspin投放印尼slots游戏广告的优势尤为显著…

汽车零部件材料耐候性测试氙光太阳辐射系统试验箱

概述 汽车零部件等领域的材料耐候性测试是一项关键的质量控制环节&#xff0c;它关乎汽车部件在各种气候条件下的性能表现和寿命。塑料件光照老化实验箱&#xff0c;即氙灯老化试验箱&#xff0c;在其中扮演着至关重要的角色。通过模拟自然环境中的光照、温度、湿度等条件&…

顺序表(C语言详细版)

1. 线性表 线性表(lina list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串...... 线性表在逻辑上是线性结构&#xff0c;也就是说连续的一条直线。但是在物理结构上并…

开源205W桌面充电器,140W+65W升降压PD3.1快充模块(2C+1A口),IP6557+IP6538

开源一个基于IP6557和IP6538芯片的205W升降压快充模块&#xff08;140W65W&#xff09;&#xff0c;其中一路C口支持PD3.1协议&#xff0c;最高输出28V5A&#xff0c;另一路是A口C口&#xff0c;最高输出65W&#xff08;20V3.25A&#xff09;&#xff0c;可搭配一个24V10A的开关…

Ubuntu20.04 安装 cudatookit 12.2 + cudnn 安装

最简约的部署Ubuntu20.04深度学习环境的教程 1. 安装Ubuntu20.04 系统 B站详细的安装教程 简约安装版 2. 安装Nvidia显卡驱动 我参考了各种资料&#xff0c;重装系统&#xff0c;完美解决开机显示器黑屏无法进入桌面的情况 黑屏问题主要是由linux内核更新导致&#xff0c;…