当前位置: 首页 > news >正文

算法通关村第6关【白银】| 树的层次遍历问题

一、基本层次遍历问题

1.二叉树的层次遍历

思路:使用队列可以很好的保存遍历状态,出队将结点左右子结点入队,用size记录下一层的元素个数,这样就能区分出层了 

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();while(size>0){TreeNode node = queue.remove();list.addLast(node.val);if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(list);}return res;}
}

2.二叉树的层次遍历II

 思路:此题和上一题大同小异,只需要在添加结果集的时候头插法就可以了。

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> list = new LinkedList<>();while(size>0){TreeNode node = queue.removeFirst();size--;list.add(node.val);if(node.left!= null){queue.add(node.left);}if(node.right!= null){queue.add(node.right);}}res.add(0,list);}return res;}
}

3.锯齿形遍历 

思路:和层次遍历不同的是每层顺序奇偶方向交替,用一个变量记录当前层的变量规则,从左往右就是尾插法,从右往左就是头插法

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);int loop = 1;while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();for(int i = 0;i<size;i++){TreeNode node = queue.removeFirst();if(node.left!= null){queue.add(node.left);}   if(node.right!= null){queue.add(node.right);}if(loop%2==0){list.addFirst(node.val);}else{list.add(node.val);}}res.add(list);loop++;}return res;}
}

4.N叉树的层次遍历

 思路:此题和基本层次遍历不同的是,每次不是添加左右孩子入队而是添加孩子列表入队,把添加左右孩子替换成遍历添加列表就成。

class Solution {public List<List<Integer>> levelOrder(Node root) {if(root == null){return new LinkedList<>();}List<List<Integer>> res = new LinkedList<>();LinkedList<Node> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();LinkedList<Integer> list = new LinkedList<>();while(size>0){Node node = queue.remove();list.addLast(node.val);for(Node child : node.children){queue.add(child);}size--;}res.add(list);}return res;}
}

二、处理每层元素的问题

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

思路:还是和遍历大同小异,现在不是将所有子结点都加入结果,只取每层最大的,比较一下就行

class Solution {public List<Integer> largestValues(TreeNode root) {if(root == null){return new LinkedList<>();}List<Integer> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();int max = Integer.MIN_VALUE;while(size>0){TreeNode node = queue.remove();if(node.val>max){max = node.val;}if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(max);}return res;}
}

 2.每个树行的平均值

 思路:和上一题找最大值没什么差别,每层相加除以size就可以。

class Solution {public List<Double> averageOfLevels(TreeNode root) {if(root == null){return new LinkedList<>();}List<Double> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();Double mean = 0.0;for(int i = 0;i<size;i++){TreeNode node = queue.remove();mean += node.val;if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}}res.add(mean/size);}return res;}
}

3.二叉树的右视图

思路:层次遍历,最后一个元素加入结果集就行。 

class Solution {public List<Integer> rightSideView(TreeNode root) {if(root == null){return new LinkedList<>();}List<Integer> res = new LinkedList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.addFirst(root);while(!queue.isEmpty()){int size = queue.size();TreeNode node = root;while(size>0){node = queue.remove();if(node.left != null){queue.addLast(node.left);}if(node.right != null){queue.addLast(node.right);}size--;}res.add(node.val);}return res;}
}

4.找树最小角的值

思路:1)层次遍历,记录下每层第一个元素

2)从右往左层次遍历,最后一个元素

//方法一
class Solution {public int findBottomLeftValue(TreeNode root) {if(root == null){return -1;}int res = -1;LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(queue.size()>0){int size = queue.size();res = queue.get(0).val;while(size>0){TreeNode node = queue.remove();size--;if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}}}return res;}
}//方法二
class Solution {public int findBottomLeftValue(TreeNode root) {if(root == null){return -1;}int res = -1;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNode node = queue.poll();res = node.val;if(node.right != null){queue.offer(node.right);}   if(node.left != null){queue.offer(node.left);}}return res;}
}

相关文章:

算法通关村第6关【白银】| 树的层次遍历问题

一、基本层次遍历问题 1.二叉树的层次遍历 思路&#xff1a;使用队列可以很好的保存遍历状态&#xff0c;出队将结点左右子结点入队&#xff0c;用size记录下一层的元素个数&#xff0c;这样就能区分出层了 class Solution {public List<List<Integer>> levelOr…...

Qt与电脑管家3

1.ui页面设计技巧 最外面的widget&#xff1a; 上下左右的margin都置相同的值 这里有4个widget&#xff0c;做好一个后&#xff0c;后面3个可以直接复制.ui文件&#xff0c;然后进行微调即可。 2.现阶段实现的效果&#xff1a; 3.程序结构&#xff1a; btn1--->btn btn1---…...

Jmeter 快速生成测试报告

我们使用Jmeter工具进行接口测试或性能测试后一般是通过察看结果数、聚合报告等监听器来查看响应结果。如果要跟领导汇报测试结果&#xff0c;无法直接通过监听器的结果来进行展示和汇报&#xff0c;因为太low了&#xff0c;因此测试完成后去整理一个数据齐全且美观的报告是非常…...

消息队列——RabbitMQ(一)

MQ的相关概念 什么事mq MQ(message queue)&#xff0c;从字面意思上看&#xff0c;本质是个队列&#xff0c;FIFO 先入先出&#xff0c;只不过队列中存放的内容是 message 而已&#xff0c;还是一种跨进程的通信机制&#xff0c;用于上下游传递消息。在互联网架构中&#xff…...

人工智能在机器学习中的八大应用领域

文章目录 1. 自然语言处理&#xff08;NLP&#xff09;2. 图像识别与计算机视觉3. 医疗诊断与影像分析4. 金融风险管理5. 预测与推荐系统6. 制造业和物联网7. 能源管理与环境保护8. 决策支持与智能分析结论 &#x1f389;欢迎来到AIGC人工智能专栏~探索人工智能在机器学习中的八…...

vue3+ts使用vue-i18n

vue3ts使用vue-i18n 1、安装插件 npm install --save vue-i18nyarn add vue-i18n2、配置文件 locale/index.ts import { createI18n } from vue-i18n import zhCN from ./lang/zh-CN import enUS from ./lang/en-USexport const LOCALE_OPTIONS [{ label: 中文, value: zh…...

在Ubuntu上安装和设置RabbitMQ服务器,轻松实现外部远程访问

文章目录 前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道 4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 RabbitMQ是一个在 AMQP(高级消息队列协议)基…...

Redis多机实现

Background 为啥要有多机--------------1.容错 2.从服务器分担读压力。 主从结构一大难题------------如何保障一致性&#xff0c;对这个一致性要求不是很高&#xff0c;因为redis是用来做缓存的 同时我们要自动化进行故障转移-------哨兵机制&#xff0c;同时哨兵也可能cra…...

ClickHouse安装及部署

文章目录 Docker快速安装Ubuntu预编译安装包安装检查是否支持SSE4.2使用预编译安装包 Tgz安装包配置文件修改修改密码配置远程访问 其他主机访问文章参考 Docker快速安装 本地pull镜像 docker run -d --name ch-server --ulimit nofile262144:262144 -p 9000:9000 -p 8123:81…...

[HarekazeCTF2019]Easy Notes-代码审计

文章目录 [HarekazeCTF2019]Easy Notes-代码审计 [HarekazeCTF2019]Easy Notes-代码审计 登录之后有几个功能点&#xff0c;可以添加节点&#xff0c;然后使用Export导出 我们查看源码&#xff0c; 我们发现想要拿到flag的条件时$_SESSION[admin]true 如果我们能够控制sessio…...

nginx-location正则

一 Nginx的location语法 location [||*|^~] /uri/ { … } 严格匹配。如果请求匹配这个location&#xff0c;那么将停止搜索并立即处理此请求~ 区分大小写匹配(可用正则表达式)~* 不区分大小写匹配(可用正则表达式)!~ 区分大小写不匹配!~* 不区分大小写不匹配^~ 如果把这个前缀…...

微信小程序胶囊位置计算,避开胶囊位置

由于小程序在不同的手机上顶部布局会发生变化&#xff0c;不能正确避开胶囊位置&#xff0c;所以通过官方给出的胶囊信息&#xff0c;可以计算出胶囊位置&#xff0c;并避开 图示例&#xff1a; 此处思路是&#xff0c;获取胶囊底部位置&#xff0c;并拉开10个px 计算出来的…...

快速指南:使用Termux SFTP通过远程进行文件传输——”cpolar内网穿透“

文章目录 1. 安装openSSH2. 安装cpolar3. 远程SFTP连接配置4. 远程SFTP访问4. 配置固定远程连接地址 SFTP&#xff08;SSH File Transfer Protocol&#xff09;是一种基于SSH&#xff08;Secure Shell&#xff09;安全协议的文件传输协议。与FTP协议相比&#xff0c;SFTP使用了…...

记录一个用C#实现的windows计时执行任务的服务

记录一个用C#实现的windows计时执行任务的服务 这个服务实现的功能是每天下午六点统计一次指定路径的文件夹大小 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Diagnostics; using System.IO; using Syst…...

“深入剖析JVM内部机制:了解Java虚拟机的工作原理“

标题&#xff1a;深入剖析JVM内部机制&#xff1a;了解Java虚拟机的工作原理 摘要&#xff1a;本文将深入剖析JVM内部机制&#xff0c;详细介绍Java虚拟机的工作原理。我们将探讨JVM的组成部分、类加载过程、内存管理、垃圾回收以及即时编译等关键概念。此外&#xff0c;还将提…...

golang远程开发调试设置vscode插件失败解决方法记录

golang远程开发&#xff0c;插件安装失败 Failed to find the "go" binary in either GOROOT() or PATH(/root/.vscode-server/bin/b3e4e68a0bc097f0ae7907b217c1119af9e03435/bin/remote-cli:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/g…...

数据结构:二叉树及相关操作

文章目录 前言一、树的概念及结构1.什么是树2. 树的相关概念3.树的表示 二、二叉树概念及结构1.二叉树概念2.特殊的二叉树3.二叉树的性质4.二叉树的存储结构 三、平衡二叉树实现1.创建树和树的前中后遍历1.前中后遍历2.创建树且打印前中后遍历 2.转换为平衡二叉树和相关操作1.转…...

4.物联网LWIP之C/S编程,stm32作为服务器,stm32作为客户端,代码的优化

LWIP配置 服务器端实现 客户端实现 错误分析 一。LWIP配置&#xff08;FREERTOS配置&#xff0c;ETH配置&#xff0c;LWIP配置&#xff09; 1.FREERTOS配置 为什么要修改定时源为Tim1&#xff1f;不用systick&#xff1f; 原因&#xff1a;HAL库与FREERTOS都需要使用systi…...

【C语言】扫雷游戏(可展开)——超细教学

&#x1f6a9;纸上得来终觉浅&#xff0c; 绝知此事要躬行。 &#x1f31f;主页&#xff1a;June-Frost &#x1f680;专栏&#xff1a;C语言 &#x1f525;该篇将运用数组来实现 扫雷游戏。 目录&#xff1a; &#x1f31f;思路框架测试游戏 &#x1f31f;测试部分函数实现&am…...

数据的深海潜行:数据湖、数据仓库与数据湖库之间的微妙关系

导言&#xff1a;数据的重要性与存储挑战 在这个信息爆炸的时代&#xff0c;数据已经成为企业的核心资产&#xff0c;而如何高效、安全、便捷地存储这些数据&#xff0c;更是每个组织面临的重大挑战。 数据作为组织的核心资产 数据在过去的几十年里从一个辅助工具演变成企业的…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...