2024.2.8
题目来源
我的题解
方法一 层序遍历
使用层序遍历，先判断x或y是否是根节点，若是则x和y必然不可能是堂兄弟节点。每次遍历当前层时判断下一层是否出现x和y，若x和y分别出现在该节点的左右节点上，则x和y不是堂兄弟节点；若在下一层x和y没有同时出现，则x和y必然不可能是堂兄弟节点；其余情况x和y是堂兄弟节点
时间复杂度：O(n)。遍历整棵树的时间
空间复杂度：O(n)。使用的队列空间
public boolean isCousins(TreeNode root, int x, int y) {
if(root.val==x||root.val==y)
return false;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int sz=queue.size();
//count记录x和y在下一层出现的次数
int count=0;
for(int i=0;i<sz;i++){
TreeNode t=queue.poll();
//f判断x和y是不是同一个父节点
int f=0;
if(t.left!=null){
if(t.left.val==x||t.left.val==y){
count++;
f++;
}
queue.offer(t.left);
}
if(t.right!=null){
if(t.right.val==x||t.right.val==y) {
count++;
f++;
}
queue.offer(t.right);
}
if(f==2)
return false;
}
//下一层只有x或者y
if(count==1){
return false;
}
if(count==2)
break;
}
return true;
}
方法二 深度优先遍历
从根节点开始，对树进行一次遍历，在遍历的过程中维护「深度」以及「父节点」这两个信息。当遍历到 x 或 y 节点时，就将信息记录下来；当这两个节点都遍历完成了以后，就可以退出遍历的过程，判断它们是否为堂兄弟节点了。实际就是在遍历过程中记录每个节点的深度、父节点
时间复杂度：O(n)。遍历整棵树的时间
空间复杂度：O(n)。使用的队列空间
TreeNode xParent;
int xDeepth;
TreeNode yParent;
int yDeepth;
public boolean isCousins(TreeNode root, int x, int y) {
if(root.val==x||root.val==y)
return false;
dfs(0,root,x,y,null);
return xDeepth==yDeepth&&xParent!=yParent;
}
public void dfs(int deepth,TreeNode node,int x,int y,TreeNode parent){
if(node==null){
return ;
}
if(node.val==x){
xParent=parent;
xDeepth=deepth;
}else if(node.val==y){
yParent=parent;
yDeepth=deepth;
}
dfs(deepth+1,node.left,x,y,node);
dfs(deepth+1,node.right,x,y,node);
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈
标签：node,2024.2,遍历,val,int,力扣,二叉树,root,节点 From： https://blog.csdn.net/weixin_42075274/article/details/137201990