993. 二叉树的堂兄弟节点

[力扣原题链接](https://leetcode-cn.com/problems/cousins-in-binary-tree/)

## 题目

在二叉树中，根节点位于深度 `0` 处，每个深度为 `k` 的节点的子节点位于深度 `k+1` 处。

如果二叉树的两个节点深度相同，但 **父节点不同** ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 `root` ，以及树中两个不同节点的值 `x` 和`y` 。

只有与值 `x` 和 `y` 对应的节点是堂兄弟节点时，才返回 `true` 。否则，返回 `false`。

**示例 1:**

![](/media/202105/2021-05-17_204312.png)
```
输入：root = [1,2,3,4], x = 4, y = 3
输出：false
```

**示例 2:**

![](/media/202105/2021-05-17_204340.png)
```
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
```

**示例 3:**

![](/media/202105/2021-05-17_204357.png)
```
输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false
```

**提示：**

* 二叉树的节点数介于 `2` 到 `100` 之间。
* 每个节点的值都是唯一的、范围为 `1` 到 `100` 的整数。

## 思路（无脑操作）

依次搜索x,y在书中的深度和父节点，借助全局变量同时获得x/y的深度和父节点，比较深度相等并且父节点的值不同即可获得结果。

## 代码

语言：Java

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode parent;  // 父节点
    private int depth;         // 深度

public boolean isCousins(TreeNode root, int x, int y) {
        int xDepth = 0;
        int yDepth = 0;
        TreeNode xParent = new TreeNode(-1);
        TreeNode yParent = new TreeNode(-1);
        boolean xNode = isNode(root, null, x, 0);
        if(xNode) {
            xParent = this.parent;
            xDepth = depth;
        }
        boolean yNode = isNode(root, null, y, 0);
        if(yNode) {
            yParent= this.parent;
            yDepth = this.depth;
        }

return ((yDepth == xDepth) && (xParent.val != yParent.val));
    }

/**
     * 遍历搜索树,找到搜索节点是否属于树的结点
     * 若属于,获得该节点的深度,父节点,并返回true
     * 若不属于,返回false
     * 
     * @param root
     * @param parent
     * @param val
     * @param depth
     * @return
     */
    public boolean isNode(TreeNode root, TreeNode parent, int val, int depth) {
        if(root == null) {
            return false;
        }
        if(val == root.val) {
            this.parent = parent;
            this.depth = depth;
            return true;
        }
        // 无法匹配则先搜索左子树,若找到直接返回true
        if(isNode(root.left, root, val, depth+1)) {
            return true;
        } else {
            // 左子树找不到,搜索右子树
            return isNode(root.right, root, val, depth+1);
        }

}
}
```

## 力扣官方代码
**思路：**
用2个全局变量接收x,y的深度和父节点，这样可以同时进行搜索，减少时间消耗

```
class Solution {
    // x 的信息
    int x;
    TreeNode xParent;
    int xDepth;
    boolean xFound = false;

// y 的信息
    int y;
    TreeNode yParent;
    int yDepth;
    boolean yFound = false;

public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        dfs(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

public void dfs(TreeNode node, int depth, TreeNode parent) {
        if (node == null) {
            return;
        }

if (node.val == x) {
            xParent = parent;
            xDepth = depth;
            xFound = true;
        } else if (node.val == y) {
            yParent = parent;
            yDepth = depth;
            yFound = true;
        }

// 如果两个节点都找到了，就可以提前退出遍历
        // 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
        if (xFound && yFound) {
            return;
        }

dfs(node.left, depth + 1, node);

if (xFound && yFound) {
            return;
        }

dfs(node.right, depth + 1, node);
    }
}
```