-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day-7_Cousins_in_Binary_Tree.py
65 lines (43 loc) · 1.66 KB
/
Day-7_Cousins_in_Binary_Tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
'''
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:
The number of nodes in the tree will be between 2 and 100.
Each node has a unique integer value from 1 to 100.
'''
# 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:
bfs = deque([(root, None)])
while bfs:
n = len(bfs)
parent = None
foundone = False
for _ in range(n):
curr, par = bfs.popleft()
if curr.val==x or curr.val==y:
if not foundone:
foundone = True
parent = par
else: return parent!=par
if curr.right:
bfs.append((curr.right, curr))
if curr.left:
bfs.append((curr.left, curr))
return False