580，BFS和DFS解二叉树的堂兄弟节点
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)，栈的深度，最坏情况下二叉树退化为链表形状。
●
●
●
●