当前位置: 首页 > 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 &…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...