查看原文
其他

580,BFS和DFS解二叉树的堂兄弟节点

博哥 数据结构和算法 2022-05-01

You are never wrong to do the right thing. 

坚持做对的事,你永远不会错。

问题描述



来源:LeetCode第993题

难度:简单


在二叉树中,根节点位于深度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就是宽度优先搜索,一层一层的遍历。这题使用BFS是最容易想到的,BFS遍历首先会使用一个队列,把每一层的节点都加入到队列中,对于同一层的节点我们可以认为他们辈分是一样的,要么是亲兄弟节点,要么是堂兄弟节点。


首先判断两个节点值是否是亲兄弟:

  • 如果是就返回false。

  • 如果不是,在判断他们是否都在同一层,如果在同一层,说明他们是堂兄弟节点,返回true。

  • 否则遍历完了,说明他们不在同一层,不是堂兄弟节点。

1public boolean isCousins(TreeNode root, int x, int y) {
2    //两个队列一个存放树的节点,一个存放节点对应的值
3    Queue<TreeNode> queue = new LinkedList<>();
4    Queue<Integer> value = new LinkedList<>();
5    queue.add(root);
6    value.add(root.val);
7    //如果队列不为空,说明树的节点没有遍历完,就继续遍历
8    while (!queue.isEmpty()) {
9        //BFS是从上到下一层一层的打印,levelSize表示
10        //当前层的节点个数
11        int levelSize = queue.size();
12        for (int i = 0; i < levelSize; i++) {
13            //节点和节点值同时出队
14            TreeNode poll = queue.poll();
15            value.poll();
16            //首先判断x和y是否是兄弟节点的值,也就是判断他们的父节点
17            //是否是同一个
18            if (poll.left != null && poll.right != null) {
19                //如果是亲兄弟节点,直接返回false
20                if ((poll.left.val == x && poll.right.val == y) ||
21                        (poll.left.val == y && poll.right.val == x)) {
22                    return false;
23                }
24            }
25            //左子节点不为空加入到队列中
26            if (poll.left != null) {
27                queue.offer(poll.left);
28                value.offer(poll.left.val);
29            }
30            //右子节点不为空加入到队列中
31            if (poll.right != null) {
32                queue.offer(poll.right);
33                value.offer(poll.right.val);
34            }
35        }
36        //判断当前层是否包含这两个节点的值,如果包含就是堂兄弟节点
37        if (value.contains(x) && value.contains(y))
38            return true;
39    }
40    return false;
41}

时间复杂度:O(n),n是节点的个数,最差情况下遍历到最后一层。

空间复杂度:O(n),使用两个队列,队列中一个存放的是节点,一个存放的是节点的值。


DFS解决



前序遍历,中序遍历,和后续遍历都可以认为是DFS。我们遍历的时候如果找到x节点或者y节点,就记录下他们的父节点和深度,最后再判断。


  • 如果深度不一样,说明不在同一层,那么他俩的辈分就不一样,肯定不是堂兄弟节点。

  • 如果深度一样,说明在同一层,是同一辈的,但还要判断他们的父亲是否是同一个,如果是同一个说明他俩是亲兄弟,否则就是堂兄弟。


代码如下

1private TreeNode xParent = null;//x的父节点
2private TreeNode yParent = null;//y的父节点
3private int xDepth = -1;//x的深度
4private int yDepth = -2;//y的深度
5
6public boolean isCousins(TreeNode root, int x, int y) {
7    dfs(root, null, x, y, 0);
8    //如果他俩的深度一样,也就是在同一层,又不是同一个父亲,那么他俩
9    //就是堂兄弟节点,否则不是
10    return xDepth == yDepth && xParent != yParent ? true : false;
11}
12
13public void dfs(TreeNode root, TreeNode parent, int x, int y, int depth) {
14    if (root == null)
15        return;
16    if (root.val == x) {
17        //如果找到了x节点,就把他的父节点和深度记录下来
18        xParent = parent;
19        xDepth = depth;
20    } else if (root.val == y) {
21        //如果找到了y节点,就把他的父节点和深度记录下来
22        yParent = parent;
23        yDepth = depth;
24    }
25    //如果确定他俩是堂兄弟节点了,直接返回,不用再往下遍历了
26    if (xDepth == yDepth && xParent != yParent)
27        return;
28    dfs(root.left, root, x, y, depth + 1);
29    dfs(root.right, root, x, y, depth + 1);
30}

时间复杂度:O(n),n是节点的个数,最差情况下遍历所有节点。

空间复杂度:O(n),栈的深度,最坏情况下二叉树退化为链表形状。


574,DFS和BFS解单词拆分

532,BFS解打开转盘锁

531,BFS和动态规划解完全平方数

473,BFS解单词接龙


截止到目前我已经写了500多道算法题了,为了方便大家阅读,我把部分算法题整理成了pdf文档,目前有1000多页,大家可以在公众号中回复关键字“pdf”即可获取下载链接。


你点的每个赞,我都认真当成了喜欢

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存