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

Constraints:

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

``````class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue<TreeNode*> q{{root}};
bool isX = false, isY = false;
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
TreeNode *cur = q.front(); q.pop();
if (cur->val == x) isX = true;
if (cur->val == y) isY = true;
if (cur->left && cur->right) {
int left = cur->left->val, right = cur->right->val;
if ((left == x && right == y) || (left == y && right == x)) return false;
}
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
if (isX && isY) return true;
if (isX || isY) return false;
}
return false;
}
};
``````

``````class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
int depthX = 0, depthY = 0;
bool sameParent = false;
helper(root, x, y, 0, depthX, depthY, sameParent);
return !sameParent && depthX == depthY;
}
void helper(TreeNode* node, int x, int y, int cur, int& depthX, int& depthY, bool& sameParent) {
if (!node) return;
if (node->val == x) depthX = cur;
if (node->val == y) depthY = cur;
if (node->left && node->right) {
int left = node->left->val, right = node->right->val;
if ((left == x && right == y) || (left == y && right == x)) sameParent = true;
}
helper(node->left, x, y, cur + 1, depthX, depthY, sameParent);
helper(node->right, x, y, cur + 1, depthX, depthY, sameParent);
}
};
``````

``````class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
unordered_map<int, pair<int, int>> m;
helper(root, 0, -1, m);
return m[x].first == m[y].first && m[x].second != m[y].second;
}
void helper(TreeNode* node, int depth, int parent, unordered_map<int, pair<int, int>>& m) {
if (!node) return;
m[node->val] = {depth, parent};
helper(node->left, depth + 1, node->val, m);
helper(node->right, depth + 1, node->val, m);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/993

Binary Tree Level Order Traversal

https://leetcode.com/problems/cousins-in-binary-tree/

https://leetcode.com/problems/cousins-in-binary-tree/discuss/238536/My-Easy-Recursive-C%2B%2B-Solution

https://leetcode.com/problems/cousins-in-binary-tree/discuss/239376/Java-BFS-time-and-space-beat-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation