算法通关村第六关——原来如此简单
层次遍历:又叫广度优先遍历。就是从根节点开始,先访问根节点下面一层全部元素,再访问之后的层次,直到访问完二叉树的最后一层。
我们先看一下基础的层次遍历题,力扣102题:给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。
分析:先将根节点
root放到队列queue中,接着遍历队列。遍历当前层次的节点时,如果这个节点还有子节点,就将其加入队列中;如果当前层次遍历完了,就将队列的长度重新指向新的队列长度sizeOfQueue,这时队列长度就是下一层的节点个数。

function TreeNode(val, left, right) {this.val = (val === undefined ? 0 : val)this.left = (left === undefined ? null : left)this.right = (right === undefined ? null : right)}/*** 层次遍历,自顶向下 *@param: {TreeNode} root;*@return {number[][]}* * */function levelOrder(root) {if (!root) {return [];}let result = [];let queue = [];queue.push(root);while (queue.length > 0) {let size = queue.length;const tempList = [];for (let i = 0; i < size; i++) {let t = queue.shift();tempList.push(t.val);if (t.left !== null) {queue.push(t.left);}if (t.right !== null) {queue.push(t.right);}}result.push(tempList);}return result;}
在上一题的基础上,我们看一下力扣515题,给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。
分析:这其实就是先进行层次遍历,之后找出每一层的最大值即可。我们用一个变量
maxValue来记录当前得到的最大值。和本层的每一个节点的值进行比较。
/*** @param {TreeNode} root* @return {number[]}* */
function largestValues(root) {if (!root) {return [];}const largestValues = []; // 存放每一层的最大值let queue = [root];while (queue.length > 0) {let sizeOfQueue = queue.length;let largestValue = -Number.MAX_VALUE;while (sizeOfQueue > 0) {sizeOfQueue--;const treeNode = queue.shift();largestValue = Math.max(largestValue, treeNode.val) // 比较大小if (treeNode.left !== null) {queue.push(treeNode.left);}if (treeNode.right !== null) {queue.push(treeNode.right);}}largestValues.push(largestValue); // 把每一层最大值加入存放最大值的数组}return largestValues;
}
我们再来看一下力扣199题,给给定一个二叉树的根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
**分析:**这道题也是层次遍历的变种题,我们思考一下,既然需要我们找到每一层最右边节点的值,那在我们遍历每一层节点的时候,我们已经将这层节点放入队列,是不是只需要判定一下
for循环的索引值是否等于队列长度 - 1即可,这样我们找到了最右边的节点,同样的如果for循环的索引值= 0,那么找到的就是这层最左边的节点。
function rightSideView(root) {const result = [];let queue = [root];if (!root) {return [];}while (queue.length > 0) {const sizeOfQueue = queue.length;for (let indexOfQueue = 0; indexOfQueue < sizeOfQueue; indexOfQueue++) {const treeNode = queue.shift();if (treeNode.left) {queue.push(treeNode.left);}if (treeNode.right) {queue.push(treeNode.right);}// 如果是队列的最后一个节点就是每一层最右边的节点if (indexOfQueue === sizeOfQueue - 1) {result.push(treeNode.val);}}}return result;
}
总结
掌握了层序遍历的方法,就可以对很多二叉树的变种题做出应对。
相关文章:
算法通关村第六关——原来如此简单
层次遍历:又叫广度优先遍历。就是从根节点开始,先访问根节点下面一层全部元素,再访问之后的层次,直到访问完二叉树的最后一层。 我们先看一下基础的层次遍历题,力扣102题:给你一个二叉树,请你返…...
企业权限管理(八)-登陆使用数据库认证
Spring Security 使用数据库认证 在 Spring Security 中如果想要使用数据进行认证操作,有很多种操作方式,这里我们介绍使用 UserDetails 、 UserDetailsService来完成操作。 UserDetails public interface UserDetails extends Serializable { Collecti…...
第一百二十五天学习记录:C++提高:STL-deque容器(下)(黑马教学视频)
deque插入和删除 功能描述: 向deque容器中插入和删除数据 函数原型: 两端插入操作: push_back(elem); //在容器尾部添加一个数据 push_front(elem); //在容器头部插入一个数据 pop_back(); //删除容器最后一个数据 pop_front(); //删除容器…...
案例12 Spring MVC入门案例
网页输入http://localhost:8080/hello,浏览器展示“Hello Spring MVC”。 1. 创建项目 选择Maven快速构建web项目,项目名称为case12-springmvc01。 2.配置Maven依赖 <?xml version"1.0" encoding"UTF-8"?><project xm…...
【React】精选10题
1.React Hooks带来了什么便利? React Hooks是React16.8版本中引入的新特性,它带来了许多便利。 更简单的状态管理 使用useState Hook可以在函数组件中方便地管理状态,避免了使用类组件时需要继承React.Component的繁琐操作。 避免使用类组件…...
VS Spy++进程信息获取
查看进程中窗口信息。 Spy使用介绍 Windows下的程序及热键监视神器——Spy Word进程获取...
Java课题笔记~ SpringMVC概述
1.1 SpringMVC简介 SpringMVC 也叫Spring web mvc。是Spring 框架的一部分,在Spring3.0 后发布的。 1.2 SpringMVC的优点 基于MVC 架构 基于 MVC 架构,功能分工明确。解耦合。 容易理解,上手快,使用简单 就可以开发一个注解…...
SOPC之NIOS Ⅱ遇到的问题
记录NIOS Ⅱ中遇到的报错 一、NIOS II中Eclipse头文件未找到 问题:Unresolved inclusion: "system.h"等 原因:编译器无法找到头文件所在路径 解决方法: 在文件夹中找到要添加的头文件,并记录下其路径,如…...
uniapp uni-datetime-picker 日期和光标靠右
如果想在uni-datetime-picker组件中将日期和光标靠右,您可以使用自定义样式来实现。首先,您需要在页面的样式文件中定义一个类,用于定制uni-datetime-picker组件的样式。例如,你可以在App.vue或者页面的样式文件中添加以下代码&am…...
关于axios请求中的GET、POST、PUT、DELETE的一些认知
这篇写的特别好。而本文主要从实习用途中展开,不专业。 浅谈HTTP中Get、Post、Put与Delete的区别 1、Get 1、目前Get禁止使用requestBody形式传递值,如果使用了,后端会一直报错,让你确认是否有传递参数。 2、举例,模…...
go-zero 是如何做路由管理的?
原文链接: go-zero 是如何做路由管理的? go-zero 是一个微服务框架,包含了 web 和 rpc 两大部分。 而对于 web 框架来说,路由管理是必不可少的一部分,那么本文就来探讨一下 go-zero 的路由管理是怎么做的,…...
Springboot集成ip2region离线IP地名映射-修订版
title: Springboot集成ip2region离线IP地名映射 date: 2020-12-16 11:15:34 categories: springboot description: Springboot集成ip2region离线IP地名映射 1. 背景2. 集成 2.1. 步骤2.2. 样例2.3. 响应实例DataBlock2.4. 响应实例RegionAddress 3. 打开浏览器4. 源码地址&…...
智能驾驶系列报告之一:智能驾驶 ChatGPT时刻有望来临
原创 | 文 BFT机器人 L3 功能加速落地,政策标准有望明确 L2 发展日益成熟,L3 功能加速落地。根据市场监管总局发布的《汽车驾驶自动化分级》与 SAE发布的自动驾驶分级标准,自动驾驶主要分为 6 个级别(0 级到 5 级,L0 …...
设计HTML5文档结构
定义清晰、一致的文档结构不仅方便后期维护和拓展,同时也大大降低了CSS和JavaScript的应用难度。为了提高搜索引擎的检索率,适应智能化处理,设计符合语义的结构显得很重要。 1、头部结构 在HTML文档的头部区域,存储着各种网页元…...
vue echarts中按钮点击后修改值 watch数据变化后刷新图表
1 点击按钮 {feature: {myBtn1: {show: true,title: 反转Y轴,showTitle: true,icon: path://M512 0A512 512 0 1 0 512 1024A512 512 0 0 0 512 0M320 320V192h384v128zM128 416V288h256v128zM320 704V576h384v128zM128 800V672h256v128z,onclick: () > {dataSetting.rever…...
React antd tree树组件 - 父子节点没有自动关联情况下 - 显示半选、全选状态以及实现父子节点互动
实现的效果图如下: 如Ant Design Vue 中所示,并没有提供获取半选节点的方法,当设置checked和checkStrictly时,父子节点也不再自动关联了 前提:从后端可以获取的数据分别是完整的树型数据、所有选中的节点数据&#…...
优漫动游 大厂需要什么样的ui设计师呢?
通常来说大公司UI设计的流程主要是这样的:创意-头脑风暴-策划方案-交互设计&评审-美术设计&评审-开发实施,不过实际上大多数公司都有自己的一套流程,源于公司的基因、公司组织体系、公司领导风格。一起了解大厂需要什么样的ui设计师呢…...
TiDB Bot:用 Generative AI 构建企业专属的用户助手机器人
本文介绍了 PingCAP 是如何用 Generative AI 构建一个使用企业专属知识库的用户助手机器人。除了使用业界常用的基于知识库的回答方法外,还尝试使用模型在 few shot 方法下判断毒性。 最终,该机器人在用户使用后,点踩的比例低于 5%࿰…...
uniapp 使用canvas画海报(微信小程序)
效果展示: 项目要求:点击分享绘制海报,并实现分享到好友,朋友圈,并保存 先实现绘制海报 <view class"data_item" v-for"(item,index) in dataList" :key"index"click"goDet…...
TiDB 应急运维脚本,更加方便的管理TiDB集群
TiDB 应急运维脚本,更加方便的管理TiDB集群 使用方法 使用方法:[tidblocalhost ~]$ which tiup ~/.tiup/bin/tiup编辑脚本,MYSQL_PASSWD 和 PORT 根据实际替换 [tidblocalhost ~]$ vi ~/.tiup/bin/ti#version 1.1 #author guanguanglei ##…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
