题目大意：
二叉树的堂兄弟节点
在二叉树中，根节点位于深度 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的整数。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=993
解题思路分析：
看到二叉树的题目，你应该立刻意识到使用dfs或者bfs来解题。本题也不例外，使用dfs解题会非常方便。
我们从根节点开始向下dfs递归遍历二叉树的每一个节点。dfs函数中，我们需要定义level和parent两个变量来代表当前层以及当前节点的父节点。递归函数中，如果当前节点值等于x，那么我们记录下x所在的level，以及x的父节点。同时结束递归。同理，如果当前节点值等于y，那么我们记录下y所在的level，以及y的父节点。同时结束递归。
另外如果当前节点既不是x也不是y的话，我们继续向下递归，如果当前节点存在右子节点，我们递归至其右子节点，参数level加一，parent节点变为当前节点。同理，如果当前节点存在左子节点，我们递归至其左子节点，参数level加一，parent节点变为当前节点。
所有递归结束后，我们查看x和y的level是否相同，并且他们的父节点是否不同，如果满足上述条件的话，那么返回true，反之返回false。
实现代码：
int xLevel, yLevel;
int xParent, yParent;
public boolean isCousins(TreeNode root, int x, int y) {
dfs(root,x,y,0,0);
return xLevel>0&&xLevel==yLevel&&xParent!=yParent;
}
void dfs(TreeNode root, int x, int y, int level, int parent){
if(root.val==x){
xLevel=level;
xParent=parent;
return;
}
if(root.val==y){
yLevel=level;
yParent=parent;
return;
}
if(root.left!=null) dfs(root.left,x,y,level+1,root.val);
if(root.right!=null) dfs(root.right,x,y,level+1,root.val);
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Cousins in Binary Tree.
Memory Usage: 37.1 MB, less than 7.14% of Java online submissions for Cousins in Binary Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-993-cousins-in-binary-tree-解题思路分析/