LeetCode 993. 二叉树的堂兄弟节点

2021年9月14日 7点热度 0条评论 来源: 数据结构和算法

截止到目前我已经写了 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),栈的深度,最坏情况下二叉树退化为链表形状。

    原文作者:数据结构和算法
    原文地址: https://blog.csdn.net/abcdef314159/article/details/120281425
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。