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

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

11 人参与  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)
  • 赞助本站

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

最新文章

  • 爱,一触就破无广告_妹妹夏夏孟夏人气小说_小说后续在线阅读_无删减免费完结_
  • 他死后前妻疯魔了彩蛋(顾煜迟林筱棠)全书在线下载阅读完美终章小说大结局
  • 此后锦书休寄周窈音全文最新章节(周窈音)全文免费阅读无弹窗大结局_周窈音免费阅读
  • 弹幕说我是捞女?反手收购男主公司养鸡(林朝曦沈墨川)_弹幕说我是捞女?反手收购男主公司养鸡
  • 没给寡嫂抢到La******,老公把我和儿子做成蜡像(顾云州沈云烟)_没给寡嫂抢到La******,老公把我和儿子做成蜡像顾云州沈云烟
  • 出狱后,假千金靠玄术杀疯了(顾九音霍霆修)_出狱后,假千金靠玄术杀疯了
  • 养妹偷我认亲玉佩当上千金,男友当场分手超长版_玉佩陈雨柔养父母一口气看完_小说后续在线阅读_无删减免费完结_
  • 抽卡后,气运之子怎么都缠上来了小说(夏挽棠)(抽卡后,气运之子怎么都缠上来了)全书+后续+结局在线阅读
  • 前传爱意随风消逝续集:全文+番外乔清浅宋轻舟:结局+番外新上热文
  • 宋昭黎陆铭绪(假如从没拥抱你)前文+全本完整阅读预售作品抢先看
  • 终章小说搬空海港!我携军舰嫁军官躺赢了完结篇(温婉历战)已更新+延伸(搬空海港!我携军舰嫁军官躺赢了)清爽版
  • 贵妻在上:废材老公来护航完结篇(贵妻在上:废材老公来护航)章节目录+章节前文(宋锦瑶霍少霆)全章无套路在线

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

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