-
Notifications
You must be signed in to change notification settings - Fork 3
/
Cousins in Binary Tree
91 lines (82 loc) · 2.9 KB
/
Cousins in Binary Tree
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
Problem Statement:
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
Solution:
# 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:
check=[0,0]
d=0
depth=[0,0]
stack=[root]
while stack:
temp=[]
d+=1
for i in stack:
if i.left:
if i.left.val== x:
check[0]=i.val
depth[0]=d
elif i.left.val==y:
check[1]=i.val
depth[1]=d
temp.append(i.left)
if i.right:
if i.right.val==x:
check[0]=i.val
depth[0]=d
elif i.right.val==y:
check[1]=i.val
depth[1]=d
temp.append(i.right)
if temp:
stack=temp
else:
break
return check[0]!=check[1] and depth[0]==depth[1]
"""
############## Recursive ################
self.parents=[0,0]
self.depths=[0,0]
self.depth=0
def checkdepth(root,x,y):
if not root:
return
self.depth+=1
if root.left:
if root.left.val==x:
self.depths[0]=self.depth
self.parents[0]=root.val
elif root.left.val==y:
self.depths[1]=self.depth
self.parents[1]=root.val
checkdepth(root.left,x,y)
if root.right:
if root.right.val==x:
self.depths[0]=self.depth
self.parents[0]=root.val
elif root.right.val==y:
self.depths[1]=self.depth
self.parents[1]=root.val
checkdepth(root.right,x,y)
self.depth-=1
checkdepth(root,x,y)
#print(self.depths,self.parents)
return self.depths[0]==self.depths[1] and self.parents[0]!=self.parents[1]
"""