可视化图解算法39: 输出二叉树的右视图
1. 题目
描述
请根据二叉树的前序遍历,中序遍历恢复二叉树,并打印出二叉树的右视图
数据范围: 0≤n≤10000 要求: 空间复杂度 O(n),时间复杂度 O(n)
如输入[1,2,4,5,3],[4,2,5,1,3]时,通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树:
所以对应的输出为[1,3,5]。
示例1
输入:
[1,2,4,5,3],[4,2,5,1,3]
返回值:
[1,3,5]
2. 解题思路
本题其实包括两部分,即先根据前序遍历,中序遍历恢复二叉树,再并打印出二叉树的右视图。对于二叉树的回复可以参考上一篇文章《可视化图解算法38:重建二叉树》,本篇重点讲解如何打印出二叉树的右视图。
对于二叉树的右视图,可以先将二叉树进行层序遍历,对于层序遍历的结果,输出每一行的最后一个元素即可。二叉树的层序遍历可以参考《可视化图解算法23:二叉树的层序遍历》。
具体思路如下:
如果文字描述的不太清楚,你可以参考视频的详细讲解。
-
Python版本:数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1372250
-
Java版本:哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ep1367462
-
Golang版本:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1364784
3. 编码实现
核心代码如下:
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** 求二叉树的右视图* @param preOrder int整型一维数组 先序遍历* @param inOrder int整型一维数组 中序遍历* @return int整型一维数组*/
func solve(preOrder []int, inOrder []int) []int {// write code here//构建二叉树tree := buildTree(preOrder, inOrder)//二叉树输出右视图return rightSideView(tree)
}func rightSideView(root *TreeNode) []int {res := make([]int, 0)// 1. 定义一个队列,保存每一层的所有节点;先将根节点放入队列queue := []*TreeNode{root}//2. 执行出队列操作:出队列的左右子树再重新入队列for len(queue) > 0 {count := len(queue) //获取一层中的节点数量,并进行遍历//如果当前层有节点,将节点数据添加到数组中,左、右子树添加到队列中for i := 0; i < count; i++ {node := queue[0] //获取队列的顶部元素queue = queue[1:] //删除队列的顶部元素if i == count-1 {res = append(res, node.Val) //存入右视图的元素:一行中的最后一个}//若是左右子节点存在,则存入左右节点作为下一个层次if node.Left != nil {queue = append(queue, node.Left)}if node.Right != nil {queue = append(queue, node.Right)}}}return res
}func buildTree(pre []int, vin []int) *TreeNode {// 2. 递归终止条件(pre、vin长度一样,只需要判断一个即可)if len(pre) == 0 {return nil}// 1. 问题分解(递推公式)// 1.1 根节点(前序遍历的第一个值)root := &TreeNode{Val: pre[0]}// 1.2 根节点在中序遍历中的位置index := getIndex(vin, pre[0])// 1.3 以根节点索引为分割线,将数组pre、vin分为左右两部分root.Left = buildTree(pre[1:index+1], vin[:index]) //左部分构成左子树(切片截取:左闭右开)root.Right = buildTree(pre[index+1:], vin[index+1:]) //右部分构成右子树return root
}func getIndex(vin []int, data int) int {for index, d := range vin {if d == data {return index //pre 和 vin 均无重复元素}}return 0
}
具体完整代码你可以参考下面视频的详细讲解。
-
Python版本:数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1372250
-
Java版本:数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1367462
-
Golang版本:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ep1364784
4.小结
对于二叉树的右视图:①即先根据前序遍历,中序遍历恢复二叉树;②通过层序遍历再并打印出二叉树的右视图。
《数据结构与算法》深度精讲课程正式上线啦!七大核心算法模块全解析:
✅ 链表
✅ 二叉树
✅ 二分查找、排序
✅ 堆、栈、队列
✅ 回溯算法
✅ 哈希算法
✅ 动态规划
无论你是备战笔试面试、提升代码效率,还是突破技术瓶颈,这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡,与千名开发者共同进阶!
-
Python编码实现:数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ss897667807
-
Java编码实现:哔哩哔哩_bilibili
https://www.bilibili.com/cheese/play/ss161443488
-
Golang编码实现:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕
https://www.bilibili.com/cheese/play/ss63997
对于二叉树的相关算法,我们总结了一套【可视化+图解】方法,依据此方法来解决相关问题,算法变得易于理解,写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
今日佳句:两岸猿声啼不住,轻舟已过万重山。
相关文章:
可视化图解算法39: 输出二叉树的右视图
1. 题目 描述 请根据二叉树的前序遍历,中序遍历恢复二叉树,并打印出二叉树的右视图 数据范围: 0≤n≤10000 要求: 空间复杂度 O(n),时间复杂度 O(n) 如输入[1,2,4,5,3],[4,2,5,1,3]时,通过前序遍历的结…...
数据库基础复习笔记
数据库 相关概念 名称全称检查数据库存储数据的仓库,数据是有组织的进行存储DataBase(DB)数据库管理系统操作和管理数据库的大型软件DataBase Management System(DBMS)SQL操作关系型数据库的编程语言,定义了一套操作关系型数据库…...
鸿蒙OSUniApp 实现一个精致的日历组件#三方框架 #Uniapp
使用 UniApp 实现一个精致的日历组件 前言 最近在开发一个约会小程序时,需要实现一个既美观又实用的日历组件。市面上虽然有不少现成的组件库,但都不太符合我们的设计需求。于是,我决定从零开始,基于 UniApp 自己实现一个功能完…...
Kotlin 协程实战:实现异步值加载委托,对值进行异步懒初始化
在实际开发中,我们经常遇到这样的场景。 需要立即初始化但计算成本高昂的值 val expensiveValue calculateExpensiveValue() 可能引发阻塞的初始化操作 val resource loadResourceFromNetwork()这些场景通常需要满足以下需求: 异步加载:…...
MySQL增删查改进阶
文章目录 一、数据库备份二、数据库约束2.1 NOT NULL2.2 UNIQUE:唯一约束2.3 DEFAULT:默认值约束 一、数据库备份 在MySQL当中,数据库是如何备份的呢?主要通过三种方式进行备份: 数据库最终都是存储在硬盘上…...
Tensorflow2保存和加载模型
1、model.save() and model.load() 此种方法可保存模型的结构、参数等内容。加载模型后无需设置即可使用! 保存模型: model.save(my_model.h5) 加载模型: # 加载整个模型 loaded_model tf.keras.models.load_model(my_model.h5) 注意&…...
通过泛域名解析把二级域名批量绑定到wordpress的指定页面
通过泛域名解析将二级域名批量绑定到WordPress的指定页面,需要完成两个主要步骤:一是设置泛域名解析,二是配置服务器和WordPress以实现二级域名到指定页面的映射。以下是详细的操作方法: 1. 设置泛域名解析 在域名注册商的管理后…...
BGP联邦+反射器实验
一、实验拓扑 二、IP规划 骨干: 172.16.0.0/30 ---- R2-R3 172.16.0.4/30 ---- R3-R4 172.16.0.8/30 ---- R4-R7 172.16.0.12/30 ---- R6-R7 172.16.0.16/30 ---- R5-R6 172.16.0.20/30 ---- R2-R5 非骨干: 172.16.2.0/24 ---- R2的环回 2.2.2.2/32 17…...
3天云南旅游规划
云南的主要旅游城市和景点。昆明作为云南的省会,拥有丰富的自然景观和适合短途游玩的地方。 第一天可以安排在昆明市内和周边,方便游玩。 第二天,可以考虑去大理,这是云南的著名旅游城市,距离昆明大约2小时的车程。大理…...
SCDN能够运用在物联网加速当中吗?
在当今的科技化时代当中,物联网已经广泛渗透在各个领域行业当中,随着物联网规模的不断扩大,数据信息的传输速度和网络稳定性成为企业需要重视的两点因素,而SCDN也成为安全内容分发网络作为一种融合了内容加速和安全防护的技术&…...
Go语言八股之Mysql基础详解
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…...
计算机视觉----基础概念、卷积
一、概述 1.计算机视觉的定义 计算机视觉(Computer Vision)是一个跨学科的研究领域,主要涉及如何使计算机能够通过处理和理解数字图像或视频来自动进行有意义的分析和决策。其目标是使计算机能够从视觉数据中获取高层次的理解,类似于人类的视觉处理能力。 具体来说,计算机…...
Problem E: List练习
1.题目描述 运用List完成下面的要求: 1) 创建一个List,在List中增加三个工人,基本信息如下: 姓名 年龄 工资 Tom 18 3000 Peter 25 3500 Mark 22 3200 2) 插入一个工人,信息为:姓名:Robert࿰…...
12-串口外设
一、串口外设的基本概述 1、基本定义 串口通信,通过在通信双方之间以比特位(bit)的形式逐一发送或接收数据,实现了信息的有效传递。其通信方式不仅简单可靠,而且成本很低。 2、stm32的串口 下面是两个MCU的数据交互&…...
C++(2)
二、面向对象基础 1. 类与对象 1.1 核心概念 类(Class) 定义:抽象描述具有共同特征和行为的对象模板本质:代码复用的蓝图,定义数据(属性)与操作(行为࿰…...
GMT之Bash语言使用
GMT的操作有自己的逻辑和“命令”,但GMT是可以用Bash语言控制的,所以常常以.sh为后缀写GMT程序。 GMT程序运行步骤如下: 采用cd ,定位到指定文件夹;以sh ***.sh运行GMT,得到结果。 另外,遇到…...
半成品的开源双系统VLA模型,OpenHelix-发表于2025.5.6
半成品的开源双系统VLA模型,OpenHelix https://openhelix-robot.github.io/ 0. 摘要 随着OpenVLA的开源,VLA如何部署到真实的机器人上获得了越来越多的关注,各界人士也都开始尝试解决OpenVLA的效率问题,双系统方案是其中一个非…...
fiftyone-dataset使用基础
1.创建dataset 将dataset写入数据库时,对于已有的dataset name会报错: 解决方法:指定覆盖写 添加参数overwriteTrue, 默认为False # 在写入数据集时,指定overwriteTrue,表示当dataset_name在数据库中已存在时&#…...
(1-4)Java Object类、Final、注解、设计模式、抽象类、接口、内部类
目录 1. Object类 1.1 equals 1.2 toString() 2.final关键字 3.注解 4. 设计模式 4.1 单例模式 4.1.1 饿汉式 4.1.3 饿汉式 VS 懒汉式 5. 抽象类&抽象方法 6. 接口 1. Object类 1.1 equals 重写Object 的equals方法,两种实现方式…...
强力巨彩谷亚推出专业智慧显示屏,满足多元场景需求
LED显示屏作为信息传播与视觉展示的关键载体,其性能和品质的提升备受关注。为响应市场对高品质显示的迫切需求,强力巨彩旗下专业智慧显示高端品牌谷亚G-ART,携多款行业领先水平的LED显示屏产品亮相,为用户带来专业、高效且节能的显…...
基于Spring AI与Hugging Face TGI构建高效聊天应用:从配置到实践全解析
基于Spring AI与Hugging Face TGI构建高效聊天应用:从配置到实践全解析 前言 在人工智能技术蓬勃发展的当下,大语言模型(LLM)的应用场景日益丰富。如何快速将 Hugging Face 生态中的强大模型部署为可通过 API 访问的服务&#x…...
MySQL视图:虚拟表的强大功能与应用实践
在数据库管理系统中,视图(View)是一种极其重要却常被忽视的功能。作为MySQL数据库的核心特性之一,视图为开发者和数据库管理员提供了数据抽象、安全控制和查询简化的强大工具。本文将全面探讨MySQL视图的概念、工作原理、创建与管理方法,以及…...
matlab插值方法(简短)
在MATLAB中,可以使用interp1函数快速实现插值。以下代码展示了如何使用spline插值方法对给定数据进行插值: x1 [23,56]; y1 [23,56]; X 23:1:56*4; Y interp1(x1,y1,X,spline);% linear、 spline其中,x1和y1是已知数据点,X是…...
【拥抱AI】Deer-Flow字节跳动开源的多智能体深度研究框架
最近发现一款可以对标甚至可能超越GPT-Researcher的AI深度研究应用,Deer-Flow(Deep Exploration and Efficient Research Flow)作为字节跳动近期开源的重量级项目,正以其模块化、灵活性和人机协同能力引发广泛关注。该项目基于 La…...
基于开源AI大模型与S2B2C生态的个人品牌优势挖掘与标签重构研究
摘要:在数字文明时代,个人品牌塑造已从传统经验驱动转向数据智能驱动。本文以开源AI大模型、AI智能名片与S2B2C商城小程序源码为技术载体,提出"社会评价-数据验证-标签重构"的三维分析框架。通过实证研究发现,结合第三方…...
2025年PMP 学习十二 第9章 项目资源管理
2025年PMP 学习十二 第9章 项目资源管理 序号过程过程组1规划资源管理规划2估算活动资源规划3获取资源执行4建设团队执行5管理团队执行6控制资源监控 项目资源管理,包括实物资源和团队资源。 文章目录 2025年PMP 学习十二 第9章 项目资源管理项目团队和 项目管理团…...
AI生成功能测试文档|测试文档
AI生成功能测试文档:链接直达 计算机功能测试文档撰写教程 链接直达:生成功能测试文档工具 一、文档概述 (一)文档目的 明确计算机功能测试的流程、方法和标准,确保测试的有效性和可靠性,为软件的质量评…...
Python 常用模块(八):logging模块
目录 一、引言:日志模块在项目开发中的重要性二、从 Django 日志配置看 Logging 模块的核心组成三、logging模块核心组件详解3.1 记录器Logger3.2 级别Level3.3 根记录器使用3.4 处理器Handler3.5 格式化器Formatter3.6 日志流3.7 日志示例 四、日志模块总结 一、引…...
入门OpenTelemetry——可观测性与链路追踪介绍
可观测性 什么是可观测性 可观察性(Observability)是从外部输出知识中推断所获得,可理解为衡量一个系统内部状态的方法。可观测性是一种能力,它能帮助你回答系统内部发生了什么——无需事先定义每种可能的故障或状态。系统的可观…...
c#队列及其操作
可以用数组、链表实现队列,大致与栈相似,简要介绍下队列实现吧。值得注意的是循环队列判空判满操作,在用链表实现时需要额外思考下出入队列条件。 设计头文件 #ifndef ARRAY_QUEUE_H #define ARRAY_QUEUE_H#include <stdbool.h> #incl…...
【Linux C/C++开发】轻量级关系型数据库SQLite开发(包含性能测试代码)
前言 之前的文件分享过基于内存的STL缓存、环形缓冲区,以及基于文件的队列缓存mqueue、hash存储、向量库annoy存储,这两种属于比较原始且高效的方式。 那么,有没有高级且高效的方式呢。有的,从数据角度上看,࿰…...
77. 组合【 力扣(LeetCode) 】
文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 77. 组合 一、题目描述 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 二、测试用例 示例 1: 输入&…...
GpuGeek全栈AI开发实战:从零构建企业级大模型生产管线(附完整案例)
目录 背景一、算力困境:AI开发者的「三重诅咒」1.1 硬件成本黑洞1.2 资源调度失衡1.3 环境部署陷阱 二、三大核心技术突破GpuGeek的破局方案2.1 分时切片调度引擎(Time-Slicing Scheduler)2.2 异构计算融合架构2.3 AI资产自动化…...
LeetCode 热题 100_颜色分类(98_75_中等_C++)(技巧)(计数;双指针)
LeetCode 热题 100_颜色分类(98_75_中等_C) 题目描述:输入输出样例:题解:解题思路:思路一(计数):思路二(双指针): 代码实现代码实现&a…...
【前端】:单 HTML 去除 Word 批注
在现代办公中,.docx 文件常用于文档编辑,但其中的批注(注释)有时需要在分享或归档前被去除。本文将从原理出发,深入剖析如何在纯前端环境下实现对 .docx 文件注释的移除,并提供完整的实现源码。最后&#x…...
TTS-Web-Vue系列:Vue3实现内嵌iframe文档显示功能
🖼️ 本文是TTS-Web-Vue系列的新篇章,重点介绍如何在Vue3项目中优雅地实现内嵌iframe功能,用于加载外部文档内容。通过Vue3的响应式系统和组件化设计,我们实现了一个功能完善、用户体验友好的文档嵌入方案,包括加载状态…...
AWS CloudTrail日志跟踪启用
问题 启用日志管理。 步骤 审计界面,如下图: 点击创建跟踪,AWS云就会记录AWS账号在云中的操作。...
PHP 编程:现代 Web 开发的基石与演进
引言 PHP(Hypertext Preprocessor)自1995年诞生以来,已成为全球最流行的服务器端脚本语言之一。尽管近年来Node.js、Python等语言在特定领域崭露头角,但PHP仍占据着超过78%的网站市场份额(W3Techs数据)。本…...
NAT/代理服务器/内网穿透
目录 一 NAT技术 二 内网穿透/内网打洞 三 代理服务器 一 NAT技术 跨网络传输的时候,私网不能直接访问公网,就引入了NAT能讲私网转换为公网进行访问,主要解决IPv4(2^32)地址不足的问题。 1. NAT原理 当某个内网想访问公网,就必…...
[已解决] VS Code / Cursor / Trae 的 PowerShell 终端 conda activate 进不去环境的常见问题
背景 PS C:\Users\Lenovo\WPSDrive\669715199_3\WPS云盘\课程\研一\ROAS5700 Robot Motion Planning and Control\Final\LaTex报告\final-v1> conda activate mpPS C:\Users\Lenovo\WPSDrive\669715199_3\WPS云盘\课程\研一\ROAS5700 Robot Motion Planning and Control\Fin…...
Kuka AI音乐AI音乐开发「人声伴奏分离」 —— 「Kuka Api系列|中文咬字清晰|AI音乐API」第6篇
导读 今天我们来了解一下 Kuka API 的人声与伴奏分离功能。 所谓“人声伴奏分离”,顾名思义,就是将一段完整的音频拆分为两个独立的轨道:一个是人声部分,另一个是伴奏(乐器)部分。 这个功能在音乐创作和…...
深度伪造对知识产权保护的新挑战与应对之策
首席数据官高鹏律师团队 在科技的飞速发展带来了诸多便利的同时,也引发了一系列复杂的法律问题,其中深度伪造技术对知识产权保护的冲击尤为显著,亟待引起广泛关注与深入探讨。 深度伪造,简单来说,是借助先进的人工智…...
【嵌入式开发-软件定时器】
嵌入式开发-软件定时器 ■ 1.■ 2.■ 3.■ 4. ■ 1. ■ 2. ■ 3. ■ 4....
3天重庆和成都旅游规划
重庆和成都都是大城市,各自都有丰富的旅游资源。如果要在三天内两头都游览,可能需要合理安排时间,确保既能体验到重庆的特色,又能在成都游览主要景点。然而,考虑到交通时间,如果从重庆到成都需要一定的时间…...
JAVA中的文件操作
文章目录 一、文件认识(一)文件的分类(二)目录结构 二、文件操作(一)File类1.属性2.构造方法3.方法 (二)File类的具体使用1.文件路径的查看2.文件的基本操作(1࿰…...
深度解析网闸策略:构建坚固的网络安全防线
深度解析网闸策略:构建坚固的网络安全防线 在数字化浪潮中,网络安全已成为企业、机构乃至国家稳定发展的关键要素。随着网络攻击手段日益复杂多样,传统的网络安全防护措施难以满足日益增长的安全需求。网闸作为一种先进的网络安全设备&#x…...
【Rust trait特质】如何在Rust中使用trait特质,全面解析与应用实战
✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,…...
滑动窗口算法笔记
力扣209 题目分析:想象一个窗口遍历着这个数组,不断扩大右边界,让r。往窗口中添加数字: 此时我们找到了这个窗口,它的和满足了大于等于target的条件,题目让我求最短的,那么我们就尝试来缩短它&…...
Problem A: 歌手打分
1.题目描述 在歌唱比赛中,共有10位评委进行打分,在计算歌手得分时,去掉一个最高分,去掉一个最低分,然后剩余的8位评委的分数进行平均,就是该选手的最终得分。输入每个评委的评分,求某选手的得分…...
容器安全-核心概述
文章摘要 本文探讨了容器安全的四个核心类别,包括环境基础设施安全、镜像安全、运行时安全和生态安全。尽管 EDR 能提供主机安全层面的部分防护,但无法覆盖容器的镜像安全和生态安全。容器的镜像安全和生态安全问题,如镜像漏洞、恶意镜像、容…...