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的基本概念基本概念:为什么使用依赖注入: 构造器注入构造器注入的基本概念:示例:…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
