当前位置:首页 » 《随便一记》 » 正文

LeetCode 993. 二叉树的堂兄弟节点_数据结构和算法

18 人参与  2021年11月06日 08:03  分类 : 《随便一记》  评论

点击全文阅读


截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public boolean isCousins(TreeNode root, int x, int y) {
    //两个队列一个存放树的节点,一个存放节点对应的值
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> value = new LinkedList<>();
    queue.add(root);
    value.add(root.val);
    //如果队列不为空,说明树的节点没有遍历完,就继续遍历
    while (!queue.isEmpty()) {
        //BFS是从上到下一层一层的打印,levelSize表示
        //当前层的节点个数
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            //节点和节点值同时出队
            TreeNode poll = queue.poll();
            value.poll();
            //首先判断x和y是否是兄弟节点的值,也就是判断他们的父节点
            //是否是同一个
            if (poll.left != null && poll.right != null) {
                //如果是亲兄弟节点,直接返回false
                if ((poll.left.val == x && poll.right.val == y) ||
                        (poll.left.val == y && poll.right.val == x)) {
                    return false;
                }
            }
            //左子节点不为空加入到队列中
            if (poll.left != null) {
                queue.offer(poll.left);
                value.offer(poll.left.val);
            }
            //右子节点不为空加入到队列中
            if (poll.right != null) {
                queue.offer(poll.right);
                value.offer(poll.right.val);
            }
        }
        //判断当前层是否包含这两个节点的值,如果包含就是堂兄弟节点
        if (value.contains(x) && value.contains(y))
            return true;
    }
    return false;
}

时间复杂度O(n)n是节点的个数,最差情况下遍历到最后一层。
空间复杂度O(n),使用两个队列,队列中一个存放的是节点,一个存放的是节点的值。

在这里插入图片描述

private TreeNode xParent = null;//x的父节点
private TreeNode yParent = null;//y的父节点
private int xDepth = -1;//x的深度
private int yDepth = -2;//y的深度

public boolean isCousins(TreeNode root, int x, int y) {
    dfs(root, null, x, y, 0);
    //如果他俩的深度一样,也就是在同一层,又不是同一个父亲,那么他俩
    //就是堂兄弟节点,否则不是
    return xDepth == yDepth && xParent != yParent ? true : false;
}

public void dfs(TreeNode root, TreeNode parent, int x, int y, int depth) {
    if (root == null)
        return;
    if (root.val == x) {
        //如果找到了x节点,就把他的父节点和深度记录下来
        xParent = parent;
        xDepth = depth;
    } else if (root.val == y) {
        //如果找到了y节点,就把他的父节点和深度记录下来
        yParent = parent;
        yDepth = depth;
    }
    //如果确定他俩是堂兄弟节点了,直接返回,不用再往下遍历了
    if (xDepth == yDepth && xParent != yParent)
        return;
    dfs(root.left, root, x, y, depth + 1);
    dfs(root.right, root, x, y, depth + 1);
}

时间复杂度O(n)n是节点的个数,最差情况下遍历所有节点。
空间复杂度O(n),栈的深度,最坏情况下二叉树退化为链表形状。


点击全文阅读


本文链接:http://zhangshiyu.com/post/30518.html

节点  队列  遍历  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1