(bfs)993. Cousins in Binary Tree

T: O(n)

S: O(n)

```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 record Step(TreeNode node, int level, TreeNode parent){};
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(root, 0, null));
        int xLevel = 0;
        TreeNode xParent = null;
        int yLevel = 0;
        TreeNode yParent = null;
        int findCount = 0;

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            if (cur.node == null) {
                continue;
            }
            if (cur.node.val == x) {
                xLevel = cur.level;
                xParent = cur.parent;
                findCount++;
            }
            if (cur.node.val == y) {
                yLevel = cur.level;
                yParent = cur.parent;
                findCount++;
            }
            if (findCount == 2) {
                break;
            }
            queue.offer(new Step(cur.node.left, cur.level+1, cur.node));
            queue.offer(new Step(cur.node.right, cur.level+1, cur.node));
        }
        return xLevel == yLevel && !xParent.equals(yParent);
    }
}

/**
BFS, record depth and parent, when find x , y compare them

 */
```