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

数据结构——二叉树层序遍历

数据结构——二叉树层序遍历

    • 107. 二叉树的层序遍历 II
    • 199. 二叉树的右视图
      • 思路:
    • 637. 二叉树的层平均值

107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

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

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

自底向上遍历,将原层序遍历的结果反转即可

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offer(root);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}list.add(itemList);}List<List<Integer>> result = new ArrayList<>();for (int i = list.size() - 1; i >= 0; i-- ) {result.add(list.get(i));}return result;}
}

199. 二叉树的右视图

199. 二叉树的右视图
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例 1:
在这里插入图片描述
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

思路:

层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize = que.size();for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}if (i == levelSize - 1) {list.add(poll.val);}}}return list;}
}

637. 二叉树的层平均值

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
在这里插入图片描述
在这里插入图片描述
层序遍历的时候把一层求个总和在取一个均值。

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root==null){return list;}que.offerLast(root);while(!que.isEmpty()){TreeNode peek = que.peekFirst();int levelSize = que.size();double levelSum = 0.0;// 统计每一层的和for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();levelSum += poll.val;if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}}list.add(levelSum / levelSize);//均值放入结果list}return list;}
}

相关文章:

数据结构——二叉树层序遍历

数据结构——二叉树层序遍历 107. 二叉树的层序遍历 II199. 二叉树的右视图思路&#xff1a; 637. 二叉树的层平均值 107. 二叉树的层序遍历 II 107. 二叉树的层序遍历 II 给你二叉树的根节点 root &#xff0c;返回其节点值 自底向上的层序遍历 。 &#xff08;即按从叶子节…...

【微机原理】8088/8086微处理器

目录 一、8088/8086的功能结构 1.总线接口部件&#xff08;BIU&#xff09; 2.执行部件&#xff08;EU&#xff09; 二、8088/8086的寄存器结构&#xff08;14个&#xff09; 溢出标志的概念 溢出和进位的区别 8086CPU是Intel系列的16位微处理器&#xff0c;他有16根数据…...

springboot第12集:DAO功能代码

在Spring Boot中&#xff0c;DAO是数据访问对象的缩写&#xff0c;它是一种设计模式用于提供对数据库操作的抽象层。通过使用DAO模式&#xff0c;我们可以将数据操作与业务逻辑分离&#xff0c;并提供一个单独的接口来执行所有的数据库操作。 在Spring Boot中&#xff0c;通常使…...

基于KZG多项式承诺方案的RLN

1. 引言 RLN——Rate-Limiting Nullifier为PSE团队主导的项目&#xff0c;源自&#xff1a; Barry White Hat 2019年博客 Semaphore RLN, rate limiting nullifier for spam prevention in anonymous p2p setting RLN&#xff08;Rate-Limiting Nullifier&#xff09;是一种…...

《站在巨人的肩膀上学习Java》

Java从诞生距今已经有28年了&#xff0c;在这段时间里&#xff0c;随着Java版本的不断迭代&#xff0c;Java新特性的不断出现&#xff0c;使得Java被使用的越来越广泛。在工程界Java语言一直是大家最喜欢的语言之一&#xff0c;Java一直排行在编程语言热门程度的前3名。 可想而…...

敏捷ACP.敏捷估计与规划.Mike Cohn.

第一部分 传统规划失败的原因 vs 敏捷规划有效的原因 传统的项目规划方式往往会让我们失望。要回答-一个 新产品的范围/进度/资源的组合问题&#xff0c;传统规划过程不一定会产生令人非常满意的答案和最终产品。以下- -些论据可以支持这个结论: ●大约2/3的项目会显著超…...

[创新工具和方法论]-01- DOE课程基础知识

文章目录 1.DOE实验设计的介绍1.1 什么是实验设计DOE?1.2 DOE的优势有哪些?1.3 如何开展DoE研究&#xff1f;步骤 2.DOE实验培训3.数据分析步骤4.实验的随机化5.偏差6.R方 相关系数假设检验 7.三因子二水平全因子设计 1.DOE实验设计的介绍 实验设计是一种安排实验和分析实验数…...

LeetCode-1033. 移动石子直到连续

题目链接 LeetCode-1033. 移动石子直到连续 题目描述 题解 题解一&#xff08;Java&#xff09; 作者&#xff1a;仲景 这题目挺难懂的&#xff0c;得画画图才能更好的理解 这也是LeetCode的尿性&#xff0c;习惯了&#xff0c;非得整这种别人看不懂的鸟语 你可以这样理解&a…...

JVM调优入门指南:掌握步骤、参数和场景

前言 作为Java开发者&#xff0c;我们经常需要优化应用的性能&#xff0c;其中JVM调优是非常重要的一部分。在本文中&#xff0c;我们将介绍JVM调优的一般步骤和方法&#xff0c;了解JVM调优参数&#xff0c;如堆大小、新生代比例、GC算法等参数的作用和配置方式&#xff0c;并…...

基于JSP+MySQL的跳蚤市场网站设计与开发

摘 要 在当今社会,网络信息已经不是什么很陌生的词汇,每天都在这个信息时代里生活着并且享受着它带来的与众不同。网络购物可以说是飞速发展的,这种购物方式逐渐的影响着人们的衣食住行。所以利用计算机实现 跳蚤市场网站设计与开发势在必行。本网站是一个校园的跳蚤市场网…...

内网穿透NPS和宝塔Nginx配合使用,开启SSL访问本地局域网网络

并非为了教学&#xff0c;仅供自己记录&#xff0c;方便下次用。所以内容不会刻意花时间写的很细节详细。 1. 服务器NPS配置 NPS install安装后&#xff0c;配置文件会在其他位置&#xff0c;通过是 /etc/nps/nps.conf目录。 找到进行修改&#xff0c;主要修改的是http_proxy_p…...

ToLua框架

ToLua 是一个用于在 Unity 中为 Lua 提供 C# 语言绑定的框架。通过 ToLua&#xff0c;你可以方便地将 C# 代码暴露给 Lua 脚本&#xff0c;并在 Lua 脚本中调用 C# 类、方法和属性。 更新流程 原理&#xff1a;使用AssetBundle进行资源的更新&#xff0c;而由于lua运行时才编…...

Golang-常见数据结构Map

Map map 是一种特殊的数据结构&#xff1a;一种元素对&#xff08;pair&#xff09;的无序集合&#xff0c;pair 的一个元素是 key&#xff0c;对应的另一个元素是 value&#xff0c;所以这个结构也称为关联数组或字典。这是一种快速寻找值的理想结构&#xff1a;给定 key&…...

基于空间矢量脉宽调制(SVPWM)的并网逆变器研究(Simulink)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

介绍tcpdump在centos中的使用方法

tcpdump是一款强大的命令行数据包分析器&#xff0c;支持多种过滤和抓包参数。下面将介绍tcpdump的常用抓包参数。当需要监控CentOS系统的网络流量或者进行网络故障排查时&#xff0c;可以使用tcpdump来捕获数据包并进行分析。 下面介绍在CentOS中使用tcpdump的方法&#xff1…...

机器学习实战:Python基于DT决策树模型进行分类预测(六)

文章目录 1 前言1.1 决策树的介绍1.2 决策树的应用 2 Scikit-learn数据集演示2.1 导入函数2.2 导入数据2.3 建模2.4 评估模型2.5 可视化决策树2.6 优化模型2.7 可视化优化模型 3 讨论 1 前言 1.1 决策树的介绍 决策树&#xff08;Decision Tree&#xff0c;DT&#xff09;是一…...

操作系统之进程同异步、互斥

引入 异步性是指&#xff0c;各并发执行的进程以各自独立的、不可预知的速度向前推进。 但是在一定的条件之下&#xff0c;需要进程按照一定的顺序去执行相关进程&#xff1a; 举例说明1&#xff1a; 举例说明2: 读进程和写进程并发地运行&#xff0c;由于并发必然导致异步性…...

你了解这2类神经性皮炎吗?常常预示着这5类疾病!

神经性皮炎属于慢性皮肤病&#xff0c;患者皮肤可出现局限性苔藓样变&#xff0c;同时伴有阵发性瘙痒。神经性皮炎易发生在颈部两侧和四肢伸侧&#xff0c;中年人是高发人群。到目前为止神经性皮炎病因还并不是很明确&#xff0c;不过一部分病人发病前常常出现精神神经方面异常…...

二叉搜索树【Java】

文章目录 二叉搜索树的性质二叉搜索树的操作遍历查找插入删除 二叉搜索树又称为二叉排序树&#xff0c;是一种具有一定性质的特殊的二叉树&#xff1b; 二叉搜索树的性质 若它的左子树不为空&#xff0c;则左子树上结点的值均小于根节点的值&#xff1b; 若它的右子树不为空&a…...

二叉树的遍历方式

文章目录 层序遍历——队列实现分析Java完整代码 先序遍历——中左右分析递归实现非递归实现——栈实现 中序遍历——左中右递归实现非递归实现——栈实现 后续遍历——左右中递归实现非递归实现——栈加标志指针实现 总结 层序遍历——队列实现 给你二叉树的根节点 root &…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

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

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

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...