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

100道面试必会算法-32-二叉树右视图用栈实现队列

100道面试必会算法-32-二叉树右视图&用栈实现队列

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

示例 1:

img

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

解决思路

解决这个问题,可以采用层序遍历二叉树的方式,并在每一层中只记录最右侧的节点值。

解决方法

  1. 初始化:首先初始化一个空列表 res 用于存储结果,并确保给定的根节点不为空。
  2. 层序遍历:利用队列来实现层序遍历,首先将根节点入队。
  3. 遍历节点:在每一层中,记录当前层的节点数,然后依次弹出队列中的节点。
  4. 记录右视图:每次弹出节点时,检查该节点是否是当前层的最后一个节点,如果是,则将其值添加到结果列表中。
  5. 入队子节点:同时,将弹出节点的左右子节点入队。
  6. 返回结果:最后返回结果列表 res

代码实现

class Solution {// 定义函数,用于获取二叉树的右视图public List<Integer> rightSideView(TreeNode root) {// 初始化结果列表List<Integer> res = new ArrayList<>();// 如果根节点为空,直接返回空结果列表if (root == null)return res;// 初始化队列,用于层序遍历二叉树LinkedList<TreeNode> queue = new LinkedList();// 将根节点入队queue.push(root);// 开始循环遍历二叉树while (!queue.isEmpty()) {// 记录当前层的节点数int count = queue.size();while (count > 0) {// 弹出队首元素TreeNode node = queue.poll();// 如果是当前层最后一个节点,将其值加入结果列表if (count == 1) {res.add(node.val);}// 将左子节点入队if (node.left != null) {queue.offer(node.left);}// 将右子节点入队if (node.right != null) {queue.offer(node.right);}count--;}}return res;}
}

时间复杂度为 O(n)

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

  • 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

示例 1:

输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

问题概述

需要设计一个队列的实现,但是使用栈作为底层数据结构。具体来说,需要实现 pushpoppeekempty 四种操作。

解决思路

为了使用栈来实现队列,可以使用两个栈,一个用于存储队列元素,另一个用于辅助操作。主要思路是保持一个栈始终为空,当需要执行 poppeek 操作时,将所有元素从一个栈中弹出并压入另一个栈,以保证队列顺序。

解决方法

  1. 初始化:使用两个栈 AB 分别用来存储队列元素和辅助操作。
  2. 入队操作 (push):将元素压入栈 A,相当于队尾入队。
  3. 出队操作 (pop):首先调用 peek 方法获取队首元素,然后从栈 B 中弹出栈顶元素,相当于队首出队,并返回队首元素。
  4. 查看队首元素 (peek):如果栈 B 不为空,直接返回栈 B 的栈顶元素;否则,如果栈 A 也为空,说明队列为空,返回 -1;否则,将栈 A 中的所有元素依次弹出并压入栈 B,以实现队列元素的倒序,然后返回栈 B 的栈顶元素。
  5. 判断队列是否为空 (empty):当栈 A 和栈 B 都为空时,说明队列为空。
class MyQueue {private Stack<Integer> A; // 栈A用来存储队列元素private Stack<Integer> B; // 栈B用来辅助操作public MyQueue() {A=new Stack<>(); // 初始化栈AB=new Stack<>(); // 初始化栈B}public void push(int x) {A.push(x); // 将元素压入栈A,相当于队尾入队}public int pop() {int re=peek(); // 获取栈B的栈顶元素,即队首元素B.pop(); // 弹出栈B的栈顶元素,相当于队首出队return re; // 返回队首元素}public int peek() {if(!B.isEmpty()) return B.peek(); // 如果栈B不为空,则直接返回栈B的栈顶元素if(A.isEmpty()) return -1; // 如果栈A也为空,说明队列为空,返回-1while(!A.isEmpty()){B.push(A.pop()); // 将栈A中的元素依次弹出并压入栈B,实现队列元素倒序}return B.peek(); // 返回栈B的栈顶元素,即队首元素}public boolean empty() {return A.isEmpty() && B.isEmpty(); // 如果栈A和栈B都为空,说明队列为空}
}}return B.peek(); // 返回栈B的栈顶元素,即队首元素}public boolean empty() {return A.isEmpty() && B.isEmpty(); // 如果栈A和栈B都为空,说明队列为空}
}

相关文章:

100道面试必会算法-32-二叉树右视图用栈实现队列

100道面试必会算法-32-二叉树右视图&用栈实现队列 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4]示例 2: 输入: [1,n…...

⽀付逻辑漏洞思路⼩集合

⼀.直接的价格修改 ⼆.修改⽀付状态 三.修改购买数量 四&#xff1a;⽀付附属值修改 ➀&#xff1a;修改优惠劵⾦额 ➁&#xff1a;修改优惠劵⾦额及业务逻辑问题 ➂&#xff1a;修改积分⾦额 ➃&#xff1a;满减修改 五&#xff1a;订单替代⽀付 六&#xff1a;⽀付接…...

嵌入式学习——Linux高级编程复习(线程)——day40

1. 线程 1.1 定义 线程是一个轻量级的进程 是一个任务被创建、调度、消亡的过程 1.2 线程和进程的区别与联系 1. 线程是CPU任务调度的最小单元 2. 进程是操作系统资源分配的最小单元 3. 线程&#xff08;Thread&#xff09;是操作系统能够进行运算调度的最小单位…...

kvm管理工具-virsh

virsh 查看全部虚拟机列表停止虚拟机列表启动虚拟机强制关闭虚拟机连接虚拟机控制台查看虚拟机的详细信息查看虚拟机接口信息查看虚拟机xml文件配置删除虚拟机 KVM&#xff08;Kernel-based Virtual Machine&#xff09;是一种基于 Linux 内核的虚拟化技术&#xff0c;允许在一…...

VisionPro的应用和入门教程

第1章 关于VisionPro 1.1 康耐视的核心技术 1. 先进的视觉系统 康耐视的视觉系统结合了高性能的图像传感器、复杂的算法和强大的计算能力&#xff0c;能够实时捕捉、分析和处理高分辨率图像。其视觉系统包括固定式和手持式两种&#xff0c;适用于各种工业环境。无论是精密电…...

整数规划问题算法例子

整数规划问题算法概述 整数规划(Integer Programming, IP)问题是优化问题的一种,其中决策变量必须取整数值。整数规划问题在许多实际应用中广泛存在,如资源分配、排班、路径优化等。 0-1背包问题旅行商问题利用线性规划库求解整数规划问题的方法 以下是两个常见的整数规划…...

C#启动一个cmd.exe多次随时输入命令并获取输出

想要实现的效果&#xff0c;程序通过Process类一次启动cmd&#xff0c;后台线程每隔一定时间&#xff0c;向其输入命令&#xff0c;获得并处理输出。 一、基本操作 首先&#xff0c;通常操作的例子一抓一大把&#xff1a; 1、通过Process启动cmd执行一条/多条&#xff08;&am…...

持续总结中!2024年面试必问 20 道分布式、微服务面试题(五)

上一篇地址&#xff1a;持续总结中&#xff01;2024年面试必问 20 道分布式、微服务面试题&#xff08;四&#xff09;-CSDN博客 九、请解释API网关在微服务架构中的作用。 API网关是微服务架构中的一个重要组件&#xff0c;它充当所有客户端请求的单一入口点&#xff0c;然后…...

Android输入法IME(三)之 管理端(IMMS)启动流程

2.2. IME管理端&#xff08;IMMS&#xff09;初始化流程 IMMS运行在system server进程中&#xff0c;属于系统服务的一部分&#xff0c;用于控制输入法的显示/隐藏、切换、绑定等操作。 涉及代码文件路径&#xff1a; IMMS运行在system server进程中&#xff0c;属于系统服务的…...

elasticsearch安装与使用(4)-搜索入门

1、创建索引 PUT /hotel {"mappings": {"properties":{"title":{"type": "text"},"city":{"type": "keyword"},"price":{"type":"double"}}} }2、写入文档 …...

【UML用户指南】-12-对高级结构建模-接口、类型和角色

目录 1、名称 2、操作 3、关系 4、理解接口 5、常用建模技术 5.1、对系统中的接缝建模 5.2、对静态类型和动态类型建模 5.2.1、对静态类型建模 5.2.2、对动态类型建模 使接口易于理解和易于访问 接口在关于一个抽象做什么的描述与关于这个抽象如何做的实现之间定义了…...

C++笔试强训day42

目录 1.最大差值 2.兑换零钱 3.小红的子串 1.最大差值 链接https://www.nowcoder.com/practice/a01abbdc52ba4d5f8777fb5dae91b204?tpId182&tqId34396&rp1&ru/exam/company&qru/exam/company&sourceUrl%2Fexam%2Fcompany&difficulty2&judgeSta…...

Docker 中运行的 MySQL 数据库与 Docker 外部的管理系统连接

步骤 1&#xff1a;运行 MySQL 容器 首先&#xff0c;确保你的 Docker 容器中运行了 MySQL 数据库。 docker run --name mysql-container -e MYSQL_ROOT_PASSWORDmy-secret-pw -d -p 3306:3306 mysql:latest--name mysql-container 为容器命名。-e MYSQL_ROOT_PASSWORDmy-sec…...

10 设备树

掌握设备树是 Linux 驱动开发人员必备的技能! 1、什么是设备树 新版本 Linux 中,ARM 相关的驱动全部采用了设备树。Linux-4.1.15 支持设备树。我们了解一下设备树的起源、重点学习一下设备树语法。 设备树:Device Tree,就是“设备”和“树”,描述设备树的文件叫做 DTS(…...

【架构分析】GPU执行GEMM矩阵运算实例演示

背景介绍 Cutlass是 NVIDIA 提供的一套用于高效实现矩阵乘法和卷积操作的 C 库。它以 CUDA 为基础&#xff0c;提供了高度优化的数学运算&#xff0c;尤其适用于GPU上的高性能并行计算。本文以GEMM矩阵运算作为实例&#xff0c;展示Cutlass在GPU上执行GEMM运算的过程 实例演示…...

从《千脑智能》看大模型

千脑智能与大模型 千脑智能介绍 世界模型千脑智能理论——对大脑的全新理解旧大脑&#xff1a;演化的历史烙印新大脑&#xff1a;智慧的创新引擎新旧大脑的互动与争斗启示与借鉴 大脑对信息的处理和建模六根六尘六识 新脑&#xff1a;智能的创新中枢旧脑&#xff1a;生存的本能…...

k8s Pods漂移时间配置

默认为300秒 apiVersion: apps/v1 kind: Deployment metadata:name: my-test spec:replicas: 1selector:matchLabels:app: my-apptemplate:metadata:labels:app: my-appspec:containers:- name: my-containerimage: nginx:latestports:- containerPort: 80tolerations:- key: &…...

Python - json 美化格式、保存文件

文章目录 读取长篇幅的 jsonl 文件时&#xff0c;我们难以了解 json 的格式&#xff0c;复制出来贴到 sojson 之类的网站&#xff0c;当数据量大的时候感觉麻烦。 不如自己写个 json 格式美化&#xff0c;然后保存到文件。 text open(file_path).readline() # 读取 jsonl 文…...

博客目录~

1、Jenkins构建打包部署前端Vue项目至Nginx-CSDN博客 2、https://blog.csdn.net/askuld/article/details/139429298 3、基于DockerJenkins实现自动部署SpringBootMaven项目-CSDN博客 4、时序数据库ClickHouse的安装使用_clickhouse安装使用-CSDN博客 5、Valid&#xff0c…...

RPC RMI 区别以及在java中的应用

文章目录 1. 简介1.1 什么是RPC1.2 什么是RMI 2. RPC与RMI的区别2.1 RPC和RMI的优缺点对比RPC的优点RPC的缺点RMI的优点RMI的缺点 2.2 选择RPC还是RMI&#xff1f;应用场景和考虑因素选择RPC的场景选择RMI的场景 3. RPC在Java框架中的应用3.1 Java中常用的RPC框架3.2 RPC在Java…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...