LC 0993 [E] Cousins in Binary Tree - ALawliet/algorithms GitHub Wiki
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
if not root or root.val == x or root.val == y:
return False
Q = deque([root])
while Q:
# this level
is_x_exist = False
is_y_exist = False
# range across the level
for _ in range(len(Q)):
node = Q.popleft()
# same depth is same level
if node.val == x:
is_x_exist = True
elif node.val == y:
is_y_exist = True
# same depth with same parent, so NOT cousins
if node.left and node.right:
if set([node.left.val, node.right.val]) == set([x, y]):
return False
if node.left: Q.append(node.left)
if node.right: Q.append(node.right)
# same depth with different parents
if is_x_exist and is_y_exist:
return True
return False