LeetCode102. 二叉树的层序遍历(2024秋季每日一题 43)

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

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

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

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

树中节点数目在范围 [ 0 , 2000 ] [0, 2000] [0,2000]
− 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 1000<=Node.val<=1000


解法一:
思路:

  • 每层一个 vector,相当于二维数组的一行
  • 每次遍历一行(一层)
  • 对于每层遍历:
    • 新创建一个 vector,用于记录下一层的节点
    • 如果当前节点做左子节点,则加入 下层的 vector 数组
    • 如果当前节点做右子节点,则加入 下层的 vector 数组
  • 逐层遍历,直到没有下一层
/*** 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>> levelOrder(TreeNode* root) {vector<vector<TreeNode*>> res;vector<vector<int>> ans;if(root == nullptr) return ans;int l = 0;while(res.size() >= l){vector<TreeNode*> v;vector<int> q;if(!l) v.push_back(root), q.push_back(root -> val);else{int n = res[l-1].size();for(int i = 0; i < n; i++){TreeNode* cur = res[l-1][i];if(cur -> left != nullptr) v.push_back(cur -> left), q.push_back(cur -> left -> val);if(cur -> right != nullptr) v.push_back(cur -> right), q.push_back(cur -> right -> val);}}if(v.size()) res.push_back(v);if(q.size()) ans.push_back(q);l++;}return ans;}
};

解法二:
思路:

  • 通过队列来进行搜索(bfs)
  • 在 bfs 基础上,遍历每层前,用 temp 变量 提前记录 当前层最后一个节点的位置
  • 遍历当前层的每个节点
    • 如果当前节点做左子节点,则加入 下层的 vector 数组
    • 如果当前节点做右子节点,则加入 下层的 vector 数组
  • 逐层遍历,直到没有下一层
/*** 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>> levelOrder(TreeNode* root) {vector<vector<int>> ans;TreeNode* q[2010];if(root == nullptr) return ans;int hh = 0, tt = -1;q[++tt] = root;vector<int> v;v.push_back(root -> val);ans.push_back(v);while(hh <= tt){int temp = tt;vector<int> v;while(hh <= temp){auto cur = q[hh++];if(cur -> left != nullptr) q[++tt] = cur -> left, v.push_back(q[tt]->val);if(cur -> right != nullptr) q[++tt] = cur -> right, v.push_back(q[tt]->val);}if(v.size()) ans.push_back(v);}return ans;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据结构 - 队列

队列也是一种操作受限的线性数据结构&#xff0c;与栈很相似。 01定义 栈的操作受限表现为只允许在队列的一端进行元素插入操作&#xff0c;在队列的另一端只允许删除操作。这一特性可以总结为先进先出&#xff08;First In First Out&#xff0c;简称FIFO&#xff09;。这意味…

【资料集】项目全周期过程管理资料、各类软件建设方案、源码梳理清单(全原件)

该资源库深度覆盖开发、运维、实施等核心流程&#xff0c;全面囊括项目从立项至结项的各类必需文档&#xff0c;如验收辅助材料、资质审核流程及投标策略方案等&#xff0c;确保项目生命周期的每个阶段都能找到相应的支持与依据。此外&#xff0c;资源库精心整理了研发流程细节…

Docker 容器 数据卷 使用

目录 常用 命令 什么是数据卷以及特点 如何挂载数据卷 数据卷容器 数据覆盖问题 修改已经建立的数据卷关系 博主wx&#xff1a;yuanlai45_csdn 博主qq&#xff1a;2777137742 想要 深入学习 5GC IMS 等通信知识(加入 51学通信)&#xff0c;或者想要 cpp 方向修改简历&…

Nuxt.js 应用中的 build:done 事件钩子详解

title: Nuxt.js 应用中的 build:done 事件钩子详解 date: 2024/10/21 updated: 2024/10/21 author: cmdragon excerpt: build:done 是 Nuxt.js 的一个生命周期钩子,它在 Nuxt 应用的打包构建器完成运行后被调用。这个钩子为开发者提供了一个在构建过程结束后执行特定逻辑的…

Java基于SpringBoot微信小程序的跳蚤市场系统设计与实现(lw+数据库+讲解等)

项目运行截图 技术框架 后端采用SpringBoot框架 Spring Boot 是一个用于快速开发基于 Spring 框架的应用程序的开源框架。它采用约定大于配置的理念&#xff0c;提供了一套默认的配置&#xff0c;让开发者可以更专注于业务逻辑而不是配置文件。Spring Boot 通过自动化配置和约…

数据分析和可视化python库orange简单使用方法

Orange 是一个基于 Python 的数据挖掘和机器学习库&#xff0c;它提供了一系列可视化工具和算法&#xff0c;用于数据分析、机器学习和数据可视化等任务。 一、主要特点 可视化界面&#xff1a;Orange 提供了直观的可视化界面&#xff0c;使得用户可以通过拖放操作构建数据分…

学习文档(5)

Redis应用 目录 Redis应用 Redis 除了做缓存&#xff0c;还能做什么&#xff1f; Redis 可以做消息队列么&#xff1f; Redis 可以做搜索引擎么&#xff1f; 如何基于 Redis 实现延时任务&#xff1f; Redis 除了做缓存&#xff0c;还能做什么&#xff1f; 分布式锁&…

AI‘林黛玉发疯文学’火了!40篇笔记涨粉30万,这是怎么做到的?五步教你!

本文背景 最近老刷到林黛玉那种阴阳怪气的“发疯文学”视频呢。在 小红书 搜了搜相关话题&#xff0c;嘿&#xff0c;带“#林黛玉”的话题浏览量有 9.8 亿之多&#xff0c;像“#林黛玉发疯文学”的标签浏览量也有七千多万次&#xff0c;“林黛玉倒拔垂杨柳”都有 1332 万次浏览…

Java--集合(三)之vectorlinkedlisthashset结构

文章目录 0.架构图1.vector解析2.LinkedList分析2.1源码分析2.2迭代器遍历的三种方式 3.set接口的使用方法3.1基本使用说明3.2基本遍历方式3.3HashSet引入3.4数组链表模拟3.5hashset扩容机制3.6hashset源码解读3.7扩容*转成红黑树机制**我的理解 0.架构图 1.vector解析 和之前介…

mysql 10 单表访问方法

01.优化的过程 对于我们这些 MySQL 的使用者来说&#xff0c; MySQL 其实就是一个软件&#xff0c;平时用的最多的就是查询功能。DBA时不时丢过来一些慢查询语句让优化&#xff0c;我们如果连查询是怎么执行的都不清楚还优化个毛线&#xff0c;所以是时候掌握真正的技术了。我…

Jupyter notebook中更改字体大小

文章目录 方法一&#xff1a;局部修改方法二&#xff1a;全局修改 Jupyter notebook提供了一个非常方便的跨平台交互代码编译环境&#xff0c;但是单元格的内的代码字体往往显示较小&#xff0c;不利于观看。本人查了很多方法来调整字体&#xff0c;后来发现既不需要更改jupyte…

HCIP-HarmonyOS Application Developer 习题(十二)

&#xff08;多选&#xff09;1、声明式开发范式的转场动画包含以下哪几种类型? A、页面间转场 B、应用间转场 C、共享元素转场 D、组件内转场 答案&#xff1a;ACD 分析&#xff1a; &#xff08;多选&#xff09;2、公共事件服务为应用程序提供哪些能力。 A、取消发布公共…

vue day08(vuex)

一、vuex 概述 1. 是什么 vuex 是一个 vue 的状态管理工具&#xff0c;状态就是数据 大白话&#xff1a;vuex 是一个插件&#xff0c;可以帮我们管理 vue 通用的数据&#xff08;多组件共享的数据&#xff09; 2. 场景 一份数据在多个组件中使用&#xff0c;并且还可以进行数据…

Facebook的隐私之战:数据保护的挑战与未来

在数字化时代&#xff0c;隐私保护成为了公众关注的焦点&#xff0c;尤其是在社交媒体巨头Facebook身上。随着用户数据泄露事件的频发&#xff0c;Facebook面临着日益严峻的隐私挑战。这些挑战不仅涉及法律法规的遵循&#xff0c;还影响着用户信任、公司声誉以及未来的发展方向…

【智能大数据分析 | 实验四】Spark实验:Spark Streaming

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈智能大数据分析 ⌋ ⌋ ⌋ 智能大数据分析是指利用先进的技术和算法对大规模数据进行深入分析和挖掘&#xff0c;以提取有价值的信息和洞察。它结合了大数据技术、人工智能&#xff08;AI&#xff09;、机器学习&#xff08;ML&a…

Chromium127编译指南 Windows篇 - 关键环境变量的设置(三)

前言 在我们的Chromium编译指南系列中&#xff0c;我们已经探讨了初始准备工作和 depot_tools 工具的配置。本篇文章将聚焦于Chromium编译过程中至关重要的环境变量设置&#xff0c;这些设置将为您的编译工作铺平道路。 1. 配置 DEPOT_TOOLS_WIN_TOOLCHAIN 环境变量 为了确保我…

vue综合指南(二)

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;Vue篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来Vuet篇专栏内容:vue综合指南(二) 目录 21、介绍虚拟DOM 22、vue生命周期的理解 23、vue父组件向子组件传递数据…

如何用VS实现动态爱心

首先下载一个easyx库 其次输入以下代码&#xff1a; 代码1 //#define _CRT_SECURE_NO_WARNINGS 1#include<easyx.h>//图形库 #include<stdio.h> #include<time.h> #include<math.h>//定义一个结构体 struct point {double x, y;COLORREF color; };COL…

瀚海微SD NAND存储功能描述(15)命令类b

1)传输的数据不得跨越物理块边界&#xff0c;除非在CSD中设置了WRITE BLK MISALIGN。如果不支持写部分块&#xff0c;则块长度-默认块长度(在CSD中给出)1 2) SDSC卡(CCS0)使用字节单位地址&#xff0c;SDHC和SDXC卡(CCS1)使用块单位地址(512字节单位)。 1) 32个写保护位(代表…

汽车行业焕新潮流涌动,联众优车以优质服务响应市场变化

随着消费者环保意识的改变及新能源汽车市场的快速发展&#xff0c;我国新能源汽车领域正掀起一股新的消费热潮&#xff0c;而旧车的合理处置问题也随之成为社会各界关注的焦点。今年4月末&#xff0c;商务部、财政部等七大部委携手颁布了《老旧汽车置换补贴实施指南》(以下简称…