说在前面
🎈今天给大家带来的是算法练习,题目为二叉树的堂兄弟节点。
题目描述
在二叉树中，根节点位于深度 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 的整数。思路分析
题目要我们求的是二叉树的堂兄弟节点，那么我们首先就要来了解一下什么是堂兄弟节点，简单来说，就是父亲不同但是树节点的深度又是相同的，那么他们就是一对堂兄弟节点，所以我们只要按照题意来，找出两个节点的父节点和节点深度并进行比较即可。这种题目我们可以使用深度优先搜索来进行解题，具体步骤如下：
以下几种情况要注意剪枝
- （1）已经找到两个节点；
- （2）已经找到第一个节点并且当前遍历深度大于第一个节点深度。
AC代码
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} x
* @param {number} y
* @return {boolean}
*/
var isCousins = function(root, x, y) {
let pre1 = '',floor1 = Infinity,res = '';
const compare = function(r,floor,pre){
if(r.val == x || r.val == y){
if(floor1 == Infinity){
floor1 = floor;
pre1 = pre;
}else{
res = (floor1 == floor && pre1 != pre);
}
return true;
}
return false;
}
const dfs = function(r,floor = 0,pre = null){
if(!r || res != '' || r.val == pre1 || floor > floor1) return;
if(compare(r,floor,pre)) return;
dfs(r.left,floor + 1,r.val);
dfs(r.right,floor + 1,r.val);
}
dfs(root);
return res;
};说在后面
🎉这里是JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
