Leetcode 3701 · Find Nearest Right Node in Binary Tree (遍历和BFS好题)
3701 · Find Nearest Right Node in Binary TreePRE
Algorithms
This topic is a pre-release topic. If you encounter any problems, please contact us via “Problem Correction”, and we will upgrade your account to VIP as a thank you.
Description
Given a binary tree with a root node root and a node u in the tree, return the node value val of the right-hand node nearest to it in the layer in which the node u is located, or -1 if the node u is the rightmost node in the current layer.
The total number of nodes is between
All nodes in the tree have node values that are unique
u is a node in a binary tree rooted at root
Example
Example 1:
Input:
root = {1,2,3,#,4,5,6}
u = 2
Output:
3
Explanation:
As shown in the figure, in the layer where node 2 is located, the nearest right node is node 3
3701_1.png
Example 2:
Input:
root = {3,1,#,#,2}
u = 1
Output:
-1
Explanation:
As shown in the figure, the layer where node 1 is located has only one node and the nearest right node is not found
解法1:遍历
采用前序遍历。当找到目标节点后,记住当前层次。那么,前序遍历再次到达该层次的时候,访问到的节点就是所求节点。
/*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/class Solution {
public:/*** @param root: The root of the binary tree* @param u: A node in root* @return: Node value of the right node*/int findNearestRightNode(TreeNode *root, TreeNode *u) {helper(root, 0, u);if (findNode) return findNode->val;return -1;}
private:bool find = false;int targetDepth = -1;TreeNode *findNode = NULL;void helper(TreeNode *root, int depth, TreeNode *u) {if (!root) return;if (findNode) return;if (find && depth == targetDepth) {findNode = root;return;}if (root == u) {find = true;targetDepth = depth;}helper(root->left, depth + 1, u);helper(root->right, depth + 1, u);}
};
写成这样也可以。这样就不用find变量了。
/*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/class Solution {
public:/*** @param root: The root of the binary tree* @param u: A node in root* @return: Node value of the right node*/int findNearestRightNode(TreeNode *root, TreeNode *u) {helper(root, 0, u);if (findNode) return findNode->val;return -1;}
private:int targetDepth = -1;TreeNode *findNode = NULL;void helper(TreeNode *root, int depth, TreeNode *u) {if (!root || findNode) return;if (root == u) {targetDepth = depth;} else if (targetDepth == depth) {findNode = root;return;}helper(root->left, depth + 1, u);helper(root->right, depth + 1, u);}
};
注意: 下面这个写法不对。
只用find是不够的,因为还有些其它同层次的节点在处理,结果会覆盖resValue。
比如说输入:root = [1,2,3,null,4,5,6], u = 4
下面会输出:6。但结果应该是5。
class Solution {
public:/*** @param root: The root of the binary tree* @param u: A node in root* @return: Node value of the right node*/int findNearestRightNode(TreeNode *root, TreeNode *u) {helper(root, 0, u);return resValue;}
private:bool find = false;int resValue = -1, targetDepth = -1;void helper(TreeNode *root, int depth, TreeNode *u) {if (!root) return;if (find && depth == targetDepth) {resValue = root->val;return;}if (root == u) {find = true;targetDepth = depth;}helper(root->left, depth + 1, u);helper(root->right, depth + 1, u);}
};
解法2: bfs
/*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/class Solution {
public:/*** @param root: The root of the binary tree* @param u: A node in root* @return: Node value of the right node*/int findNearestRightNode(TreeNode *root, TreeNode *u) {if (!root ||! u) return -1;queue<TreeNode *> q;int res = -1;bool find = false;q.push(root);while(!q.empty()) {int qSize = q.size();find = false;for (int i = 0; i < qSize; i++) {TreeNode *frontNode = q.front();q.pop();if (find) return frontNode->val;if (frontNode == u) find = true;if (frontNode->left) q.push(frontNode->left);if (frontNode->right) q.push(frontNode->right);}}return -1;}
};
相关文章:
Leetcode 3701 · Find Nearest Right Node in Binary Tree (遍历和BFS好题)
3701 Find Nearest Right Node in Binary TreePRE Algorithms This topic is a pre-release topic. If you encounter any problems, please contact us via “Problem Correction”, and we will upgrade your account to VIP as a thank you. Description Given a binary t…...
网站被攻击了,接入CDN对比直接使用高防服务器有哪些优势
网站是互联网行业中经常被攻击的目标之一。攻击是许多站长最害怕遇到的情况。当用户访问一个网站,页面半天打不开,响应缓慢,或者直接打不开,多半是会直接走开,而不是等待继续等待相应。针对网站攻击的防护,…...
location常用属性和方法
目录 Location 对象 Location 对象属性 Location 对象方法 location.assign() location.replace() location.reload() Location 对象 Location 对象包含有关当前 URL 的信息。Location 对象是 Window 对象的一个部分,可通过 window.location 属性来访问。 L…...

二分图
目录 二分图 染色法判定二分图 匈牙利算法 二分图 二分图,又叫二部图,将所有点分成两个集合,使得所有边只出现在集合之间的点之间,而集合内部的点之间没有边。二分图当且仅当图中没有奇数环。只要图中环的边数没奇数个数的&am…...

[VUE]3-路由
目录 路由 Vue-Router1、Vue-Router 介绍2、路由配置3、嵌套路由3.1、简介3.2、实现步骤3.3、⭐注意事项 4、⭐router-view标签详解 🍃作者介绍:双非本科大三网络工程专业在读,阿里云专家博主,专注于Java领域学习,擅…...

Kafka(六)消费者
目录 Kafka消费者1 配置消费者bootstrap.serversgroup.idkey.deserializervalue.deserializergroup.instance.idfetch.min.bytes1fetch.max.wait.msfetch.max.bytes57671680 (55 mebibytes)max.poll.record500max.partition.fetch.bytessession.timeout.ms45000 (45 seconds)he…...

RK3399平台入门到精通系列讲解(实验篇)共享工作队列的使用
🚀返回总目录 文章目录 一、工作队列相关接口函数1.1、初始化函数1.2、调度/取消调度工作队列函数二、信号驱动 IO 实验源码2.1、Makefile2.2、驱动部分代码工作队列是实现中断下半部分的机制之一,是一种用于管理任务的数据结构或机制。它通常用于多线程,多进程或分布式系统…...

STM32 基于 MPU6050 的飞行器姿态控制设计与实现
基于STM32的MPU6050姿态控制设计是无人机、飞行器等飞行器件开发中的核心技术之一。在本文中,我们将介绍如何利用STM32和MPU6050实现飞行器的姿态控制,并提供相应的代码示例。 1. 硬件连接及库配置 首先,我们需要将MPU6050连接到STM32微控制…...

大数据平台Bug Bash大扫除最佳实践
一、背景 随着越来越多的"新人"在日常工作以及大促备战中担当大任,我们发现仅了解自身系统业务已不能满足日常系统开发运维需求。为此,大数据平台部门组织了一次Bug Bash活动,既能提升自己对兄弟产品的理解和使用,又能…...

JavaScript 中的数组过滤
在构建动态和交互式程序时,您可能需要添加一些交互式功能。例如,用户单击按钮以筛选一长串项目。 您可能还需要处理大量数据,以仅返回与指定条件匹配的项目。 在本文中,您将学习如何使用两种主要方法在 JavaScript 中过滤数组。…...
随机森林(Random Forest)
随机森林(Random Forest)是一种集成学习方法,通过组合多个决策树来提高模型的性能和鲁棒性。随机森林在每个决策树的训练过程中引入了随机性,包括对样本和特征的随机选择,以提高模型的泛化能力。以下是随机森林的基本原…...

本地引入Element UI后导致图标显示异常
引入方式 npm 安装 推荐使用 npm 的方式安装,它能更好地和 webpack 打包工具配合使用。 npm i element-ui -SCDN 目前可以通过 unpkg.com/element-ui 获取到最新版本的资源,在页面上引入 js 和 css 文件即可开始使用。 <!-- 引入样式 --> <…...

UE5.1_UMG序列帧动画制作
UE5.1_UMG序列帧动画制作 UMG序列帧动画制作相对比较简单,不像视频帧需要创建媒体播放器那么复杂,以下简要说明: 1. 事件函数 2. 准备序列帧装入数组 3. 构造调用事件函数 4. 预览 序列帧UMG0105 5. 完成!按需配置即可。...
总结HarmonyOS的技术特点
HarmonyOS是华为自主研发的面向全场景的分布式操作系统。它的技术特点主要体现在以下几个方面: 分布式架构:HarmonyOS采用了分布式架构设计,通过组件化和小型化等方法,支持多种终端设备按需弹性部署,能够适配不同类别的…...

从0到1入门C++编程——04 类和对象之封装、构造函数、析构函数、this指针、友元
文章目录 一、封装二、项目文件拆分三、构造函数和析构函数1.构造函数的分类及调用2.拷贝函数调用时机3.构造函数调用规则4.深拷贝与浅拷贝5.初始化列表6.类对象作为类成员7.静态成员 四、C对象模型和this指针1.类的对象大小计算2.this指针3.空指针访问成员函数4.const修饰成员…...

Robot Operating System 2: Design, Architecture, and Uses In The Wild
Robot Operating System 2: Design, Architecture, and Uses In The Wild (机器人操作系统 2:设计、架构和实际应用) 摘要:随着机器人在广泛的商业用例中的部署,机器人革命的下一章正在顺利进行。即使在无数的应用程序和环境中,也…...

TinyEngine 服务端正式开源啦!!!
背景介绍 TinyEngine 低代码引擎介绍 随着企业对于低代码开发平台的需求日益增长,急需一个通用的解决方案来满足各种低代码平台的开发需求。正是在这种情况下,低代码引擎应运而生。它是一种通用的开发框架,通过对低代码平台系统常用的功能进…...

网页设计与制作web前端设计html+css+js成品。电脑网站制作代开发。vscodeDrea 【企业公司宣传网站(HTML静态网页项目实战)附源码】
网页设计与制作web前端设计htmlcssjs成品。电脑网站制作代开发。vscodeDrea 【企业公司宣传网站(HTML静态网页项目实战)附源码】 https://www.bilibili.com/video/BV1Hp4y1o7RY/?share_sourcecopy_web&vd_sourced43766e8ddfffd1f1a1165a3e72d7605...

Avalonia学习(二十)-登录界面演示
今天开始继续Avalonia练习。 本节:演示实现登录界面 在网上看见一个博客,展示Avalonia实现,仿照GGTalk,我实现了一下,感觉是可以的。将测试的数据代码效果写下来。主要是样式使用,图片加载方式。 只有前…...

Spring依赖注入的魔法:深入DI的实现原理【beans 五】
欢迎来到我的博客,代码的世界里,每一行都是一个故事 Spring依赖注入的魔法:深入DI的实现原理【beans 五】 前言DI的基本概念基本概念:为什么使用依赖注入: 构造器注入构造器注入的基本概念:示例:…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...