LeetCode 0993. 二叉树的堂兄弟节点:深度优先搜索(BFS)

【LetMeFly】993.二叉树的堂兄弟节点:深度优先搜索(BFS)

力扣题目链接:https://leetcode.cn/problems/cousins-in-binary-tree/

在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同,但 父节点不同 ,则它们是一对堂兄弟节点

我们给出了具有唯一值的二叉树的根节点 root ,以及树中两个不同节点的值 xy

只有与值 xy 对应的节点是堂兄弟节点时,才返回 true 。否则,返回 false

 

示例 1:

输入:root = [1,2,3,4], x = 4, y = 3
输出:false

示例 2:

输入:root = [1,2,3,null,4,null,5], x = 5, y = 4
输出:true

示例 3:

输入:root = [1,2,3,null,4], x = 2, y = 3
输出:false

 

提示:

  • 二叉树的节点数介于 2 到 100 之间。
  • 每个节点的值都是唯一的、范围为 1 到 100 的整数。

 

方法一:深度优先搜索(BFS)

两个节点是堂兄弟节点当且仅当两节点深度相同且父节点不同。

因此,我们写一个深度优先搜索函数,若搜到了x节点或y节点,则记录其父节点和深度。

最终看是否是堂兄弟节点即可。

  • 时间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))
  • 空间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))

AC代码

C++
class Solution {
private:int x, y;TreeNode* x_father, *y_father;int x_depth, y_depth;void dfs(TreeNode* root, int depth, TreeNode* father) {if (!root) {return ;}if (root->val == x) {x_father = father;x_depth = depth;}if (root->val == y) {y_father = father;y_depth = depth;}dfs(root->left, depth + 1, root);dfs(root->right, depth + 1, root);}
public:bool isCousins(TreeNode* root, int x, int y) {this->x = x, this->y = y;dfs(root, 0, nullptr);return x_father != y_father && x_depth == y_depth;}
};
Python
# from typing import Optional# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def dfs(self, root: Optional[TreeNode], depth: int, father: Optional[TreeNode]) -> None:if not root:returnif root.val == self.x:self.x_father = fatherself.x_depth = depthif root.val == self.y:self.y_father = fatherself.y_depth = depthself.dfs(root.left, depth + 1, root)self.dfs(root.right, depth + 1, root)def isCousins(self, root: TreeNode, x: int, y: int) -> bool:self.x = xself.y = yself.dfs(root, 0, None)return self.x_father != self.y_father and self.x_depth == self.y_depth

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136078040

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774295.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

java_error_in_pycharm.hprof文件是什么?能删除吗?

java_error_in_pycharm.hprof文件是什么?能删除吗? 🌵文章目录🌵 🌳引言🌳🌳hprof格式文件介绍🌳🌳java_error_in_pycharm.hprof文件什么情况下能删除🌳&…

【Nicn的刷题日常】之有序序列合并

1.题目描述 描述 输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。 数据范围: 1≤�,�≤1000 1≤n,m≤1000 , 序列中的值满足 0≤���≤30000 0≤val≤30000 输入描述…

Java 将TXT文本文件转换为PDF文件

与TXT文本文件,PDF文件更加专业也更适合传输,常用于正式报告、简历、合同等场合。项目中如果有使用Java将TXT文本文件转为PDF文件的需求,可以查看本文中介绍的免费实现方法。 免费Java PDF库 本文介绍的方法需要用到Free Spire.PDF for Java…

波卡 2023 四季度报告:开发者数量位列加密生态前三,五项新技术将于今年发布

作者:Nicholas Garcia|Messari 研究分析师 编译:OneBlock 原文:https://messari.io/report/state-of-polkadot-q4-2023?utm_mediumorganic_social&utm_sourcetwitter_messari&utm_campaignstate_of_polkadot_q4_2023 …

07:Kubectl 命令详解|K8S资源对象管理|K8S集群管理(重难点)

Kubectl 命令详解|K8S资源对象管理|K8S集群管理 kubectl管理命令kubectl get 查询资源常用的排错命令kubectl run 创建容器 POD原理pod的生命周期 k8s资源对象管理资源文件使用资源文件管理对象Pod资源文件deploy资源文件 集群调度的规则扩容与缩减集群更…

Mysql-Explain-使用说明

Explain 说明 explain SELECT * FROM tb_category_report;id:SELECT识别符,这是SELECT查询序列号。select_type:表示单位查询的查询类型,比如:普通查询、联合查询(union、union all)、子查询等复杂查询。table&#x…

[设计模式Java实现附plantuml源码~行为型]请求的链式处理——职责链模式

前言: 为什么之前写过Golang 版的设计模式,还在重新写Java 版? 答:因为对于我而言,当然也希望对正在学习的大伙有帮助。Java作为一门纯面向对象的语言,更适合用于学习设计模式。 为什么类图要附上uml 因为很…

多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测

多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测 目录 多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预…

YOLOv8改进 | 利用训练好权重文件计算YOLOv8的FPS、推理每张图片的平均时间(科研必备)

一、本文介绍 本文给大家带来的改进机制是利用我们训练好的权重文件计算FPS,同时打印每张图片所利用的平均时间,模型大小(以MB为单位),同时支持batch_size功能的选择,对于轻量化模型的读者来说,本文的内容对你一定有帮助,可以清晰帮你展示出模型速度性能的提升以及轻量…

极致成本,如何基于容器计算服务 ACS 打造企业级幻兽帕鲁私服 SaaS 服务?

作者:韩运韬(青炽) 《幻兽帕鲁》是一款最近大热的开放世界生存游戏。据报道。上市不到一周,《幻兽帕鲁》销量已突破 700 万份,成为名副其实的现象级游戏。根据游戏数据库网站 SteamDB 的数据显示,《幻兽帕…

QTabWidget和QTabBar控件样式设置(qss)

QTabWidget和QTabBar控件样式设置 1、QTabWidget样式可自定义的有哪些示例:效果图 2、QTabBar样式可自定义的有哪些示例效果图 1、QTabWidget样式可自定义的有哪些 QTabWidget::pane{} 定义tabWidgetFrameQTabWidget::tab-bar{} 定义TabBar的位置QTabWidget::tab{}定…

性能篇:如何解决高并发下 I/O 瓶颈?

我们可以有效地解决高并发下I/O瓶颈的问题,提升系统的性能。当然,实际场景中的优化可能涉及到更多的细节和技术,但希望这篇文章能为大家提供一些思路和方法。​ 引言 大家好,我是小米!今天我们来聊一个在高并发场景…

【Netty技术专题】「原理分析系列」Netty强大特性之Native transports扩展开发实战

Netty强大特性之Native transports技术原理分析 背景介绍JNI概念介绍不同平台的JNI实现 使用Native transports库Maven的分类器(Classifier)使用Linux native transport使用MacOS/BSD native transport库构建native transport库Linux版本要求MacOS/BSD版…

制度下降算法c语言

#include<stdio.h> #include<string.h> int location0; //遍历字符串的当前位置 char arr[20]"idid*id#"; void error(); //错误提示函数 /* 每一个非终结符都构造一个函数 */ void E(char t); void Ep(char t); void T(char t); void Tp(char t);…

Python 线性回归可视化 并将回归函数放置到图像上

import matplotlib.pyplot as plt import scipy import seaborn as sns# 加载内置的数据集 df sns.load_dataset(tips)#create regplot p sns.regplot(xtotal_bill, ytip, datadf)#calculate slope and intercept of regression equation slope, intercept, r, p, sterr sci…

基于BatchNorm的模型剪枝【详解+代码】

文章目录 1、BatchNorm&#xff08;BN&#xff09;2、L1与L2正则化2.1 L1与L2的导数及其应用2.2 论文核心点 3、模型剪枝的流程 ICCV经典论文&#xff0c;通俗易懂&#xff01;论文题目&#xff1a;Learning Efficient Convolutional Networks through Network Slimming卷积后能…

《动手学深度学习(PyTorch版)》笔记7.6

注&#xff1a;书中对代码的讲解并不详细&#xff0c;本文对很多细节做了详细注释。另外&#xff0c;书上的源代码是在Jupyter Notebook上运行的&#xff0c;较为分散&#xff0c;本文将代码集中起来&#xff0c;并加以完善&#xff0c;全部用vscode在python 3.9.18下测试通过&…

CC工具箱使用指南:【获取字段的所有唯一值】

一、简介 这个工具的目的是获取选定要素图层的字段的所有唯一值。 一般就是用于查看&#xff0c;比如说看一下规划用地有多少种地类&#xff0c;都是哪些地类。 二、工具参数介绍 点击【信息获取】组里的【获取字段的所有唯一值】工具&#xff1a; 即可打开下面的工具框界面…

Codeforces Round 923 (Div. 3)E. Klever Permutation 找规律,有共同区间

Problem - E - Codeforces 目录 Source of idea: 思路&#xff1a; 代码&#xff1a; 另一个up的找规律的解法&#xff1a; Source of idea: Codeforces Round 923(A-F题解) - 哔哩哔哩 (bilibili.com) 思路&#xff1a; 上面up分析的很好。两个相邻区间也就端点不一样&…

干货总结!Dockerfile编写优秀实践

Dockerfile 优秀实践 1. 善用.dockerignore文件 Docker 是CS架构&#xff0c;这就意味着 Client 和 Server 可以在不同的主机上。在构建镜像的时候&#xff0c;Client 会把所有需要的文件打包发送给 Server&#xff0c;这些发送的文件叫做 build context 默认情况下&#xf…