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

LeetCode 算法:二叉树的右视图 c++

原题链接🔗:二叉树的右视图
难度:中等⭐️⭐️

题目

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

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

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

示例 2:

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

示例 3:

输入: []
输出: []

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

题解

二叉树

  • 二叉树是一种基本的树形数据结构,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树的特点是每个节点的左子节点的值小于或等于该节点的值,而右子节点的值大于或等于该节点的值。这种特性使得二叉树非常适合用于排序和搜索操作。

二叉树右视图

  • 二叉树的右视图问题通常指的是从二叉树的右侧观察,获取从上到下每一层最右边的节点值。这个问题可以通过广度优先搜索(BFS)算法来解决,因为BFS可以按层序遍历二叉树。

广度优先搜索法

  1. 解题思路

LeetCode 上的题目 “二叉树的右视图” 要求我们从二叉树的右侧观察,打印出每一层的最后一个节点的值。这个问题可以通过多种方法解决,但最常用的是使用广度优先搜索(BFS)算法。执行广度优先搜索,左结点排在右结点之前,这样,我们对每一层都从左到右访问。因此,只保留每个深度最后访问的结点,我们就可以在遍历完整棵树后得到每个深度最右的结点。

以下是解题思路的步骤:

  1. 理解问题:首先,明确题目要求我们打印出二叉树每层的最后一个节点的值。

  2. 使用队列:由于我们需要逐层访问节点,队列是实现这一目标的理想数据结构。

  3. 初始化

    • 创建一个队列 queue 来存储当前层的节点。
    • 创建一个列表 result 来存储每层的最后一个节点的值。
  4. BFS 遍历

    • 将根节点加入队列。
    • 当队列不为空时,进行循环:
      • 记录当前层的节点数量,例如 level_size
      • 迭代 level_size 次,每次从队列中取出一个节点:
        • 如果是当前层的最后一个节点(即 queue 中没有其他节点),则将其值添加到 result 中。
        • 将当前节点的右子节点(如果有的话)加入队列。
        • 如果当前节点有左子节点,先将其加入队列,然后再处理右子节点,以确保右视图的顺序。
  5. 返回结果:遍历结束后,result 列表将包含每层的最后一个节点的值,返回这个列表。

  6. 注意:在处理节点时,如果节点为 None,则忽略它。

  7. 代码实现:根据上述思路,使用适当的编程语言实现算法。

  1. 复杂度:时间复杂度为,空间复杂度为。
  2. c++ demo
#include <iostream>
#include <vector>
#include <queue>// 定义二叉树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:// 函数用于获取二叉树的右视图std::vector<int> rightSideView(TreeNode* root) {std::vector<int> result;if (!root) return result;std::queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size(); // 当前层的节点数量for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();// 如果是当前层的最后一个节点,添加到结果中if (i == levelSize - 1) {result.push_back(node->val);}// 将左子节点入队(如果有的话)if (node->left) q.push(node->left);// 将右子节点入队(如果有的话)if (node->right) q.push(node->right);}}return result;}
};int main() {// 创建一个示例二叉树//       1//      / \//     2   3//    / \   \//   4   5   6TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->right = new TreeNode(6);Solution solution;std::vector<int> rightView = solution.rightSideView(root);// 打印右视图结果for (int val : rightView) {std::cout << val << " ";}std::cout << std::endl;// 释放二叉树内存(这里简化了释放过程,实际中需要递归释放所有节点)delete root->left->left;delete root->left->right;delete root->left;delete root->right->right;delete root->right;delete root;return 0;
}
  • 输出结果:

1 3 6

  1. 代码仓库地址:rightSideView

相关文章:

LeetCode 算法:二叉树的右视图 c++

原题链接&#x1f517;&#xff1a;二叉树的右视图 难度&#xff1a;中等⭐️⭐️ 题目 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4…...

Java 并发编程常见问题

1、线程状态它们之间是如何扭转的&#xff1f; 1、谈谈对于多线程的理解&#xff1f; 1、对于多核CPU&#xff0c;多线程可以提升CPU的利用率&#xff1b; 2、对于多IO操作的程序&#xff0c;多线程可以提升系统的整体性能及吞吐量&#xff1b; 3、使用多线程在一些场景下可…...

网络基础:静态路由

静态路由是一种由网络管理员手动配置的路由方式&#xff0c;用于在网络设备&#xff08;如路由器或交换机&#xff09;之间传递数据包。与动态路由不同&#xff0c;静态路由不会根据网络状态的变化自动调整。 不同厂商的网络设备在静态路由的配置上有些许差异&#xff1b;下面…...

库存管理系统基于spingboot vue的前后端分离仓库库存管理系统java项目java课程设计java毕业设计

文章目录 库存管理系统一、项目演示二、项目介绍三、部分功能截图四、部分代码展示五、底部获取项目源码&#xff08;9.9&#xffe5;带走&#xff09; 库存管理系统 一、项目演示 库存管理系统 二、项目介绍 基于spingboot和vue前后端分离的库存管理系统 功能模块&#xff…...

【ArcGIS AddIn插件】【可用于全国水旱灾害风险普查】全网最强洪水淹没分析插件-基于8邻域种子搜索算法-有源淹没分析算法

最近有很多GIS小伙伴咨询我关于基于8邻域种子搜索算法的有源淹没分析插件的使用方法及原理&#xff0c;咱们通过这篇文章给大家详细介绍下这款插件的运行机制。 一、插件类型及适用版本 本插件属于ArcGIS AddIn工具条插件&#xff0c;基于ArcGIS Engine10.2.2的开发环境开发的&…...

==和equals的区别(面试题)

和equals有什么区别 对于基本数据类型&#xff0c;比较的是值是否相等&#xff0c;对于引用类型则是比较的地址是否相等&#xff1b;对于equals来说&#xff0c;基本数据类型没有equals方法&#xff0c;对于引用类型equals比较的是引用对象是否相同 那针对以上结论&#xff0c…...

本地项目上传到GitHub上(李豆)

本地项目上传到GitHub上(李豆) 准备工作&#xff1a; 本地需要有 git 也需要有一个 GitHub 账号 首先需要在 GitHub 新建一个空仓库 在想要上传项目的文件夹中使用 Git 命令操作 初始化&#xff1a; git init与 github 仓库进行链接 &#xff1a;git remote add origin …...

碧海威L7云路由无线运营版 confirm.php/jumper.php 命令注入漏洞复现(XVE-2024-15716)

0x01 产品简介 碧海威L7网络设备是 北京智慧云巅科技有限公司下的产品,基于国产化ARM硬件平台,采用软硬一体协同设计方案,释放出产品最大效能,具有高性能,高扩展,产品性能强劲,具备万兆吞吐能力,支持上万用户同时在线等高性能。其采用简单清晰的可视化WEB管理界面,支持…...

redis实战-添加商户缓存

为什么要使用缓存 言简意赅&#xff1a;速度快&#xff0c;好用缓存数据存储于代码中&#xff0c;而代码运行在内存中&#xff0c;内存的读写性能远高于磁盘&#xff0c;缓存可以大大降低用户访问并发量带来的服务器读写压力实际开发中&#xff0c;企业的数据量&#xff0c;少…...

SQL游标的基本使用方法与示例

SQL游标的基本使用方法与示例 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们来探讨SQL游标的基本使用方法及示例。在数据库编程中&#xff0c;游标是一…...

还不知道工业以太网和现场总线区别???

工业以太网 工业以太网是一种专为工业环境设计的网络通信技术&#xff0c;它基于标准的以太网技术&#xff0c;但针对工业应用进行了优化。工业以太网能够适应高温、低温、防尘等恶劣工业环境&#xff0c;采用TCP/IP协议&#xff0c;与IEEE 802.3标准兼容&#xff0c;并在应用层…...

量化交易 - 策略回测

策略回测 1、什么是策略回测&#xff1f;2、策略回测的作用3、策略回测系统概述3.1策略回测中相关的指标介绍3.2量化交易策略的资金容量3.3 完整的策略回测系统包含哪些内容 1、什么是策略回测&#xff1f; 策略回测&#xff0c;也称之为策略回溯测试&#xff0c;是指利用交易…...

Java--选择排序

思想 从左向右遍历数组&#xff0c;让每个数组元素依次作为基准&#xff0c;将基准数组扫描一次&#xff0c;若有元素比基准小则标记这个元素&#xff0c;若后续元素存在比此元素更小的&#xff0c;则标记更小的元素&#xff0c;遍历完此次数组之后&#xff0c;交换基准和标记数…...

Python基础之模块和包

文章目录 1 模块和包1.1 模块和包1.1.1 模块1.1.2 包1.1.3 简单使用 1.2 import 语句1.2.1 import1.2.2 from … import 语句1.2.3 from … import * 语句 1.4 深入模块1.4.1 模块符号表1.4.2 __name__属性1.4.3 dir() 函数1.4.4 作用域 1.5 常用内置模块 1 模块和包 1.1 模块…...

基于SpringBoot漫画网站系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f31f;文末获取源码数据库&#x1f31f; 感兴趣的可以先收藏起来&#xff0c;…...

Mysql----表的约束

提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、表的约束 表的约束&#xff1a;表中一定要有约束&#xff0c;通过约束让插入表中的数据是符合预期的。它的本质是通过技术手段&#xff0c;让程序员插入正确的数据&#xff0c;约束的最终目标是保证…...

如何用 PHP 实现一个自定义爬虫框架

随着互联网的不断发展&#xff0c;信息量爆炸式增长&#xff0c;获取有价值的信息已经成为了许多人的需求。在这样的大环境下&#xff0c;爬虫技术逐渐兴起&#xff0c;成为了大数据时代的重要工具之一。爬虫技术的应用十分广泛&#xff0c;其可以用于网络舆情监测、数据分析、…...

【机器学习】机器学习的重要方法——强化学习:理论,方法与实践

目录 一、强化学习的核心概念 二、强化学习算法的分类与示例代码 三.强化学习的优势 四.强化学习的应用与挑战 五、总结与展望 强化学习&#xff1a;理论&#xff0c;方法和实践 在人工智能的广阔领域中&#xff0c;强化学习&#xff08;Reinforcement Learning, RL&…...

Linux磁盘监控思路分析

磁盘监控原理 设备又名I/O设备&#xff0c;泛指计算机系统中除主机以外的所有外部设备。 1.1 计算机分类 1.1.1 按照信息传输速度分&#xff1a; 1.低速设备&#xff1a;每秒传输信息仅几个字节或者百个字节&#xff0c;如&#xff1a;键盘、鼠标等 2.中速设备&#xff1a…...

pc端制作一个顶部固定的菜单栏

效果 hsl颜色 hsl颜色在css中比较方便 https://www.w3school.com.cn/css/css_colors_hsl.asp 色相&#xff08;hue&#xff09;是色轮上从 0 到 360 的度数。0 是红色&#xff0c;120 是绿色&#xff0c;240 是蓝色。饱和度&#xff08;saturation&#xff09;是一个百分比值…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...