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

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对比直接使用高防服务器有哪些优势

网站是互联网行业中经常被攻击的目标之一。攻击是许多站长最害怕遇到的情况。当用户访问一个网站&#xff0c;页面半天打不开&#xff0c;响应缓慢&#xff0c;或者直接打不开&#xff0c;多半是会直接走开&#xff0c;而不是等待继续等待相应。针对网站攻击的防护&#xff0c;…...

location常用属性和方法

目录 Location 对象 Location 对象属性 Location 对象方法 location.assign() location.replace() location.reload() Location 对象 Location 对象包含有关当前 URL 的信息。Location 对象是 Window 对象的一个部分&#xff0c;可通过 window.location 属性来访问。 L…...

二分图

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

[VUE]3-路由

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

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

大数据平台Bug Bash大扫除最佳实践

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

JavaScript 中的数组过滤

在构建动态和交互式程序时&#xff0c;您可能需要添加一些交互式功能。例如&#xff0c;用户单击按钮以筛选一长串项目。 您可能还需要处理大量数据&#xff0c;以仅返回与指定条件匹配的项目。 在本文中&#xff0c;您将学习如何使用两种主要方法在 JavaScript 中过滤数组。…...

随机森林(Random Forest)

随机森林&#xff08;Random Forest&#xff09;是一种集成学习方法&#xff0c;通过组合多个决策树来提高模型的性能和鲁棒性。随机森林在每个决策树的训练过程中引入了随机性&#xff0c;包括对样本和特征的随机选择&#xff0c;以提高模型的泛化能力。以下是随机森林的基本原…...

本地引入Element UI后导致图标显示异常

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

UE5.1_UMG序列帧动画制作

UE5.1_UMG序列帧动画制作 UMG序列帧动画制作相对比较简单&#xff0c;不像视频帧需要创建媒体播放器那么复杂&#xff0c;以下简要说明&#xff1a; 1. 事件函数 2. 准备序列帧装入数组 3. 构造调用事件函数 4. 预览 序列帧UMG0105 5. 完成&#xff01;按需配置即可。...

总结HarmonyOS的技术特点

HarmonyOS是华为自主研发的面向全场景的分布式操作系统。它的技术特点主要体现在以下几个方面&#xff1a; 分布式架构&#xff1a;HarmonyOS采用了分布式架构设计&#xff0c;通过组件化和小型化等方法&#xff0c;支持多种终端设备按需弹性部署&#xff0c;能够适配不同类别的…...

从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&#xff1a;设计、架构和实际应用) 摘要&#xff1a;随着机器人在广泛的商业用例中的部署&#xff0c;机器人革命的下一章正在顺利进行。即使在无数的应用程序和环境中&#xff0c;也…...

TinyEngine 服务端正式开源啦!!!

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

网页设计与制作web前端设计html+css+js成品。电脑网站制作代开发。vscodeDrea 【企业公司宣传网站(HTML静态网页项目实战)附源码】

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

Avalonia学习(二十)-登录界面演示

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

Spring依赖注入的魔法:深入DI的实现原理【beans 五】

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

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...