LeetCode算法递归类—二叉树的右视图

目录

199. 二叉树的右视图

题解:

目标:

思路:

过程:

代码:

运行结果:


给定一个二叉树的 根节点 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  

题解:

目标:

从二叉树的右侧观察,返回能够看到的节点值列表,即红色部分

 (图片采用力扣官网解题图示)

思路:

对树进行深度优先遍历,采用根右左的顺序,总是先访问右子树那么对于每一层来说,我们在这层见到的第一个结点一定是最右边的结点。

所以如果存储在每个深度访问的第一个结点,一旦我们知道了树的层数,就可以得到最终的结果数组。

过程:

  1. 首先,我们需要定义一个辅助函数 dfs 来进行深度优先搜索。该函数接收当前节点 root 和当前层数 dep 作为参数。
  2. 在 dfs 函数中,我们首先判断当前节点是否为空,如果为空则直接返回。这是终止条件。
  3. 接下来,我们判断当前层数 dep 是否大于已记录的最大层数 depth。如果是,则说明当前层是从右侧观察第一次能够看到的节点,将其值添加到结果列表 res 中,并更新最大层数 depth
  4. 然后,我们递归调用 dfs 函数,在右子节点上进行深度优先搜索,传入当前层数加 1 的值作为参数。
  5. 再次递归调用 dfs 函数,在左子节点上进行深度优先搜索,同样传入当前层数加 1 的值作为参数。
  6. 最后,返回结果列表 res

代码:

class Solution {// 记录结果List<Integer> res=new ArrayList<>();// 辅助记录树的层数int depth=-1;public List<Integer> rightSideView(TreeNode root) {if (root == null) return res; // 处理根节点为空的情况dfs(root,0);return res;}public void dfs(TreeNode root,int dep){if(root==null) return;if(depth<dep){res.add(root.val);depth++; }dfs(root.right,dep+1);dfs(root.left,dep+1);return;}
}

运行结果:

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/98993.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot的日志信息及Lombok的常用注解

文章目录 一. 日志的介绍1. 什么是日志2. 日志的作用 二. 日志的使用1. 日志格式说明2. 自定义日志的输出3. 日志级别4. 日志级别的配置5. 日志持久化6. 更简单的输出日志-Lomok7. Lombok框架实现原理以及其他常见注解 一. 日志的介绍 1. 什么是日志 日志是我们程序重要组成部…

深度学习入门-3-计算机视觉-图像分类

1.概述 图像分类是根据图像的语义信息对不同类别图像进行区分&#xff0c;是计算机视觉的核心&#xff0c;是物体检测、图像分割、物体跟踪、行为分析、人脸识别等其他高层次视觉任务的基础。图像分类在许多领域都有着广泛的应用&#xff0c;如&#xff1a;安防领域的人脸识别…

企业微信电脑端开启chrome调试

首先&#xff1a; Mac端调试开启的快捷键&#xff1a;control shift command d Window端调试开启的快捷键: control shift alt d 这边以Mac为例&#xff0c;我们可以在电脑顶部看到调试的入口&#xff1a; 然后我们点击 『浏览器、webView相关』菜单&#xff0c;勾选上…

fastadmin 下拉多级分类

要实现下图效果 一、先创建数据表 二、在目标的controll中引入use fast\Tree; public function _initialize() {parent::_initialize();$this->model new \app\admin\model\zxdc\Categorys;$tree Tree::instance();$tree->init(collection($this->model->order(…

React请求机制优化思路 | 京东云技术团队

说起数据加载的机制&#xff0c;有一个绕不开的话题就是前端性能&#xff0c;很多电商门户的首页其实都会做一些垂直的定制优化&#xff0c;比如让请求在页面最早加载&#xff0c;或者在前一个页面就进行预加载等等。随着react18的发布&#xff0c;请求机制这一块也是被不断谈起…

vue + vue-office 实现多种文件(docx、excel、pdf)的预览

支持多种文件( docx、excel、pdf)预览的vue组件库&#xff0c;支持vue2/3。也支持非Vue框架的预览。 github: 《仓库地址》 演 示&#xff1a; 《演示效果》 功能特色 一站式&#xff1a;提供docx、pdf、excel多种文档的在线预览方案&#xff0c;有它就够了简单&#xff1a…

⛳ Java 网络编程

目录 ⛳ Java 网络编程&#x1f3a8; 一、TCP / IP 协议&#x1f463; 二、IP 和 端口号&#x1f381; 三、TCP 网络层编程&#x1f3a8; 3.1、Socket⭐ 3.2、基于Socket的TCP编程 &#x1f3ed; 四、UDP网络编程&#x1f43e; 五、URL编程 ⛳ Java 网络编程 &#x1f3a8; 一…

SpringBoot + Vue 微人事项目(第三天)

左边导航菜单制作 element ui添加到Home 把侧栏的标签里面的代码拷贝到标签里面&#xff0c;显示效果如下 左侧导航栏的效果代码 <el-aside width"200px"><el-menu><el-submenu index"1"><template slot"title"><i…

NOIP2014普及组,提高组 比例简化 飞扬的小鸟 答案

比例简化 说明 在社交媒体上&#xff0c;经常会看到针对某一个观点同意与否的民意调查以及结果。例如&#xff0c;对某一观点表示支持的有1498 人&#xff0c;反对的有 902人&#xff0c;那么赞同与反对的比例可以简单的记为1498:902。 不过&#xff0c;如果把调查结果就以这种…

迈向未来的大门:人脸识别技术的突破与应用

迈向未来的大门&#xff1a;人脸识别技术的突破与应用 人脸识别&#xff1a;人脸识别的工作流程人脸识别的作用人脸识别技术的突破与应用 在深度学习人脸识别之前我们要先知道人脸识别是什么。 人脸识别&#xff1a; 人脸识别是一种基于人脸图像或视频进行身份验证或识别的技术…

【数据挖掘】使用 Python 分析公共数据【01/10】

一、说明 本文讨论了如何使用 Python 使用 Pandas 库分析官方 COVID-19 病例数据。您将看到如何从实际数据集中收集见解&#xff0c;发现乍一看可能不那么明显的信息。特别是&#xff0c;本文中提供的示例说明了如何获取有关疾病在不同国家/地区传播速度的信息。 二、准备您的…

【Linux】Centos安装 mariadb 并授权远程登陆

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; &#x1f40b; 希望大家多多支…

无涯教程-Perl - splice函数

描述 此函数从LENGTH元素的OFFSET元素中删除ARRAY元素,如果指定,则用LIST替换删除的元素。如果省略LENGTH,则从OFFSET开始删除所有内容。 语法 以下是此函数的简单语法- splice ARRAY, OFFSET, LENGTH, LISTsplice ARRAY, OFFSET, LENGTHsplice ARRAY, OFFSET返回值 该函数…

react实现对数组做增删改操作自定义hook

需求 实现对数组的增删改操作。 实现 import { useState } from react;const useArray (currList) > {const [list, setList] useState(currList);// 增const addItem (item) > {setList([...list, item]);};// 删const removeItem (idx) > {const _arr [...l…

容斥原理 博弈论(多种Nim游戏解法)

目录 容斥原理容斥原理的简介能被整除的数&#xff08;典型例题&#xff09;实现思路代码实现扩展&#xff1a;用DPS实现 博弈论博弈论中的相关性质博弈论的相关结论先手必败必胜的证明Nim游戏&#xff08;典型例题&#xff09;代码实现 台阶-Nim游戏&#xff08;典型例题&…

使用ChatGPT进行创意写作的缺点

Open AI警告ChatGPT的使用者要明白此工具的局限性&#xff0c;更不应完全依赖。作为一位创作者&#xff0c;这一点非常重要&#xff0c;应尽可能地避免让版权问题或不必要的文体问题出现在自己的作品中。[1] 毕竟使用ChatGPT进行创意写作目前还有以下种种局限或缺点[2]&#xf…

CSS自学框架之动画

这一节&#xff0c;自学CSS动画。主要学习了淡入淡出、淡入缩放、缩放、移动、旋转动画效果。先看一下成果。 优雅的过渡动画&#xff0c;为你的页面添加另一份趣味&#xff01; 在你的选择器里插入 animation 属性&#xff0c;并添加框架内置的 keyframes 即可实现&#xff0…

爬虫ip带你探索无限可能

各位程序猿大佬们&#xff0c;今天我要为大家带来一个备受关注的话题&#xff1a;爬虫ip的应用范围&#xff01;你可能会好奇&#xff0c;什么是爬虫ip&#xff1f;它在我们的日常生活中有哪些神奇的应用呢&#xff1f;让我们一起来揭开这个神秘的面纱&#xff0c;探索无限可能…

分布式链路追踪——Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

要解决的问题 如何记录请求经过多个分布式服务的信息&#xff0c;以便分析问题所在&#xff1f;如何保证这些信息得到完整的追踪&#xff1f;如何尽可能不影响服务性能&#xff1f; 追踪 当用户请求到达前端A&#xff0c;将会发送rpc请求给中间层B、C&#xff1b;B可以立刻作…

[git]gitpush提示remote: Permission to xxx.git denied to xxx

错误原因&#xff1a;git客户端你先前登录过其他用户导致&#xff0c;你用另一个账号push的时候用的先前用户 解决方法&#xff1a;删除先前用户用你想push用户重新登录 解决步骤&#xff1a; 打开控制面板-->查看方式选择大图标-->然后打开凭据管理器 找到github相关…