题目要求
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.
题目分析及思路
定义二叉树的深度：根结点的深度为0，深度为k的结点的孩子结点的深度为k+1。如果二叉树里的两个结点有相同的深度和不同的父结点，则称这两个结点为cousins。给定二叉树的根结点（每个结点的值唯一）以及两个不同结点的值，判断这两个结点是否是cousins。可以使用堆来存储结点，用字典parent和depth来存储各个结点的深度和父结点的值。遍历树的每一层，对该层结点的深度和父结点进行记录。
python代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
parent = {}
depth = {}
q = collections.deque()
q.append(root)
k = -1
while q:
k += 1
size = len(q)
for _ in range(size):
node = q.popleft()
if not node:
continue
depth[node.val] = k
q.append(node.left)
if node.left:
parent[node.left.val] = node.val
q.append(node.right)
if node.right:
parent[node.right.val] = node.val
return depth[x] == depth[y] and parent[x] != parent[y]