# 993. Cousins in Binary Tree 二叉树的堂兄弟节点

@TOC

## # 题目描述

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.

## # 解题方法

### # DFS

python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isCousins(self, root, x, y):
"""
:type root: TreeNode
:type x: int
:type y: int
:rtype: bool
"""
self.m = collections.defaultdict(tuple)
self.dfs(root, None, 0)
px, dx = self.m[x]
py, dy = self.m[y]
return dx == dy and px != py

def dfs(self, root, parent, depth):
if not root: return
self.m[root.val] = (parent, depth)
self.dfs(root.left, root, depth + 1)
self.dfs(root.right, root, depth + 1)
``````

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
m_.clear();
dfs(root, nullptr, 0);
auto px = m_[x], py = m_[y];
return px.first != py.first && px.second == py.second;
}
private:
unordered_map<int, pair<TreeNode*, int>> m_;
void dfs(TreeNode* root, TreeNode* parent, int depth) {
if (!root) return;
m_[root->val] = make_pair(parent, depth);
dfs(root->left, root, depth + 1);
dfs(root->right, root, depth + 1);
}
};
``````

### # BFS

Python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isCousins(self, root, x, y):
"""
:type root: TreeNode
:type x: int
:type y: int
:rtype: bool
"""
m = collections.defaultdict(tuple)
q = collections.deque()
q.append((root, None))
depth = 0
while q:
size = len(q)
for i in range(size):
node, p = q.popleft()
if not node: continue
m[node.val] = (p, depth)
q.append((node.left, node))
q.append((node.right, node))
depth += 1
px, dx = m[x]
py, dy = m[y]
return dx == dy and px != py
``````

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue<pair<TreeNode*, TreeNode*>> q;
q.push(make_pair(root, nullptr));
unordered_map<int, pair<TreeNode*, int>> m_;
int depth = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto p = q.front(); q.pop();
if (!p.first) continue;
m_[p.first->val] = make_pair(p.second, depth);
q.push(make_pair(p.first->left, p.first));
q.push(make_pair(p.first->right, p.first));
}
++depth;
}
auto px = m_[x], py = m_[y];
return px.first != py.first && px.second == py.second;
}
};
``````

## # 日期

2019 年 2 月 21 日 —— 一放假就再难抓紧了