# 【LeetCode】 993. Cousins in Binary Tree

## Description
> 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.

> 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`.

> 在一個二元樹中，樹根節點的深度是`0`，每個深度為`k`的節點，他們的小孩深度為`k+1`。

> 二元樹中兩個節點如果是表親，則它們擁有一樣的深度但父親不同。

> 我們給予二元樹中的`root`且所有節點都有不同的值，還有兩個不同節點中的值`x`和`y`。

> 如果`x`和`y`對應的節點是表親的話，回傳`true`。

> 提示：
> 1. 樹擁有的節點數量介於 `2` 到 `100`。
> 2. 節點中不重複的值介於 `1` 到 `100`。

## Example:

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


## Solution

* 二元樹的遍歷中，大致可以分為四種方式：
* 前序遍歷
* 中序遍歷
* 後序遍歷
* 階層遍歷
* 其中階層遍歷是使用`BFS`去跑，而結果就會按照樹的深度去跑，這剛好就是我們要的。
* 我們只要使用`BFS`，跑到`x`或`y`時去紀錄深度和父親即可。
* `BFS`的`queue`結構可以使用STL就好。

### Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:    
    void BFS(int x, int y, int& dx, int& dy, TreeNode*& px, TreeNode*& py, queue<TreeNode*>& queueNode, queue<TreeNode*>& queueParents, queue<int>& queueDepth)
    {
        if(!queueNode.empty())
        {
            TreeNode* n = queueNode.front();
            queueNode.pop();
            int d = queueDepth.front();
            queueDepth.pop();
            TreeNode* p = queueParents.front();
            queueParents.pop();
                
            if(n->val == x) 
            {
                dx = d;
                px = p;
            }
            if(n->val == y)
            {
                dy = d;
                py = p;
            }
            
            if(px && py)
                return;
            
            if(n->left)
            {
                queueNode.push(n->left);
                queueDepth.push(d + 1);
                queueParents.push(n);
            }
            if(n->right)
            {
                queueNode.push(n->right);
                queueDepth.push(d + 1);
                queueParents.push(n);
            }
            BFS(x, y, dx, dy, px, py, queueNode, queueParents, queueDepth);
        }
    }
    bool isCousins(TreeNode* root, int x, int y) {
        queue<TreeNode*> queueNode;
        queueNode.push(root);
        queue<TreeNode*> queueParents;
        queueParents.push(NULL);
        queue<int> queueDepth;
        queueDepth.push(0);
        int dx = -1;
        int dy = -1;
        TreeNode* px = NULL;
        TreeNode* py = NULL;
        
        BFS(x, y, dx, dy, px, py, queueNode, queueParents, queueDepth);
        return dx == dy && dx != -1 && px != py;
    }
};

###### tags: `LeetCode` `C++`