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的基本概念基本概念:为什么使用依赖注入: 构造器注入构造器注入的基本概念:示例:…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...

保姆级教程:在无网络无显卡的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…...

嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...

企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
boost::filesystem::path文件路径使用详解和示例
boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类,封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解,包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...