Leetcode 3701 · Find Nearest Right Node in Binary Tree (遍历和BFS好题)

2024-01-08 09:52

本文主要是介绍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好题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/583086

相关文章

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

nvm如何切换与管理node版本

《nvm如何切换与管理node版本》:本文主要介绍nvm如何切换与管理node版本问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录nvm切换与管理node版本nvm安装nvm常用命令总结nvm切换与管理node版本nvm适用于多项目同时开发,然后项目适配no

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

Node.js net模块的使用示例

《Node.jsnet模块的使用示例》本文主要介绍了Node.jsnet模块的使用示例,net模块支持TCP通信,处理TCP连接和数据传输,具有一定的参考价值,感兴趣的可以了解一下... 目录简介引入 net 模块核心概念TCP (传输控制协议)Socket服务器TCP 服务器创建基本服务器服务器配置选项服

mac安装nvm(node.js)多版本管理实践步骤

《mac安装nvm(node.js)多版本管理实践步骤》:本文主要介绍mac安装nvm(node.js)多版本管理的相关资料,NVM是一个用于管理多个Node.js版本的命令行工具,它允许开发者在... 目录NVM功能简介MAC安装实践一、下载nvm二、安装nvm三、安装node.js总结NVM功能简介N

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c