993. Cousins in Binary Tree

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Example 1:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

Example 2:

Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
Output: true

Example 3:

Input: root = [1,2,3,null,4], x = 2, y = 3
Output: false

Note:

1. The number of nodes in the tree will be between 2 and 100.
2. Each node has a unique integer value from 1 to 100.

class Solution {
    TreeNode xParent;
    TreeNode yParent;
    int xd = -1, yd = -1;
        
    public boolean isCousins(TreeNode root, int x, int y) {
        help(root, x, y, null, 0);
        return (xd == yd) && (xParent != yParent);
    }
    public void help(TreeNode root, int x, int y, TreeNode parent, int d){
        if(root == null) return;
        if(root.val == x){
            xParent = parent;
            xd = d;
        }
        if(root.val == y){
            yParent = parent;
            yd = d;
        }
        help(root.left, x, y, root, d+1);
        help(root.right, x, y, root, d+1);
    }
}

牢记前中后序遍历，depth的表达方法（下一层+1），以及parent的表示方法（从null开始，下一层parent就是这层的root）。

public boolean isCousins(TreeNode root, int A, int B) {
    if (root == null) return false;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        boolean isAexist = false;        
        boolean isBexist = false;        
        for (int i = 0; i < size; i++) {
            TreeNode cur = queue.poll();
            if (cur.val == A) isAexist = true;
            if (cur.val == B) isBexist = true;
            if (cur.left != null && cur.right != null) { 
                if (cur.left.val == A && cur.right.val == B) { 
                    return false;
                }
                if (cur.left.val == B && cur.right.val == A) { 
                    return false;
                }
            }
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        if (isAexist && isBexist)  return true;
    }
    return false;
}

这个bfs也很好，把root压进去，然后遍历q中的node，分为存在a、存在b、ab不存在且parent一样、以上都不成立（压left和right child），

一遍bfs后看看ab（xy）存不存在