Leetcode.993 二叉树的堂兄弟节点
题目链接
Leetcode.993 二叉树的堂兄弟节点 Rating : 1288
题目描述
在二叉树中,根节点位于深度 0 处,每个深度为 k 的节点的子节点位于深度 k 1 处。
如果二叉树的两个节点深度相同,但 父节点不同 ,则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root
,以及树中两个不同节点的值 x
和 y
。
只有与值 x
和 y
对应的节点是堂兄弟节点时,才返回 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
使用 bfs ,每次访问处于 同一深度 的结点。
用 x f xf xf 表示结点 x x x 的父结点,用 y f yf yf 表示结点 y y y 的父结点。
如果 x f ≠ n u l l p t r & & y f ≠ n u l l p t r xf \neq nullptr \&\& yf \neq nullptr xf=nullptr&&yf=nullptr,说明结点 x x x 和 y y y 深度相同。如果 x f ≠ y f xf \neq yf xf=yf,说明结点 x x x 和 y y y 的父结点也不相同,故 结点 x x x 和 y y y 是堂兄弟结点,返回 true
。
其他情况都返回 false
。
时间复杂度: O ( n ) O(n) O(n)
C 代码:
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue<TreeNode*> q;
q.push(root);
TreeNode *xf = nullptr , *yf = nullptr;
while(!q.empty()){
int sz = q.size();
for(int i = 0;i < sz;i ){
auto t = q.front();
q.pop();
if(t->left){
q.push(t->left);
if(t->left->val == x) xf = t;
if(t->left->val == y) yf = t;
}
if(t->right){
q.push(t->right);
if(t->right->val == x) xf = t;
if(t->right->val == y) yf = t;
}
}
//在同一层 并且 父结点不同 是堂兄弟结点
if(xf && yf && (xf != yf)) return true;
//不在同一层 不是堂兄弟结点
if(xf || yf) return false;
}
return true;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggiaic
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13