LeetCode/993. 二叉树的堂兄弟节点

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

提示：

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

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解：

本题让寻找堂兄弟结点，说的直白一点就是寻找二叉树每一层中，是否包含所给的x和y。这里需要注意的一点就是因为是堂兄弟，所以x和y不能是同一个父结点两个子结点，我们通过设置一个标记flag，如果同父则将flag置为true，最后返回即可。

具体代码如下：

public boolean isCousins(TreeNode root, int x, int y) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    boolean flags = false;

    while (!queue.isEmpty()) {
        ArrayList<Integer> temp = new ArrayList<>();
        int len = queue.size();

        for (int i = 0; i < len; i++) {
            TreeNode node = queue.poll();
            temp.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
            if (node.left != null && node.right != null) {
                if ((node.left.val == x && node.right.val == y) || (node.left.val == y && node.right.val == x)) {
                    flags = true;
                }
            }
        }
        if (temp.contains(x) && temp.contains(y) && !flags) {
            return true;
        }
    }
    return false;
}