题目描述

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
993. 二叉树的堂兄弟节点

解法1 层序遍历

根据题意，有这三种情况

1. 两个节点不在一层
2. 两个节点在一层但父节点相同
3. 两个节点在一层且父节点不同

我的思路是使用层序遍历，每次往队列里添加元素的时候，检查是否跟给的两个值相同，相同就将当前节点(层序遍历添加元素加的是左右孩子，当前节点就是根节点)添加到一个list中。一层遍历完后，判断list的长度，如果是1，说明这一层找到了一个点，说明不在一层，返回false。如果是2，判断list里的两个元素相不相同，相同说明父节点相同，返回false，否则true。

class Solution {
    //存放父节点
    List<TreeNode> pre = new LinkedList<>();

    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) {
            return false;
        }
        return CX(root, x, y);
    }

    public boolean CX(TreeNode root, int x, int y) {
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            //按层遍历
            for (int i = 0; i < n; i++) {
                root = queue.remove();
                if (root.left != null) {
                    queue.add(root.left);
                    if (root.left.val == x || root.left.val == y) {
                        if (pre.size() > 0) {
                            pre.add(1, root);
                        } else {
                            pre.add(0, root);
                        }
                    }
                }
                if (root.right != null) {
                    queue.add(root.right);
                    if (root.right.val == x || root.right.val == y) {
                        if (pre.size() > 0) {
                            pre.add(1, root);
                        } else {
                            pre.add(0, root);
                        }
                    }
                }
            }
            //为1说明一层只找到一个，不用继续遍历了，返回false
            if (pre.size() == 1) {
                return false;
            }
            //大于1判断list里两个元素是否相同，相同说明是同一个父节点，否则返回true
            if (pre.size() > 1) {
                if (pre.get(0) == pre.get(1)) {
                    return false;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
}