Sponsored
Sponsored
This approach utilizes Level Order Traversal (Breadth-First) to determine if two nodes are cousins. During traversal, track the parent and depth of each node until both target nodes are found, then verify if they qualify as cousins.
Time Complexity: O(n), where n is the number of nodes in the tree, as it requires visiting each node once.
Space Complexity: O(n) for storing the nodes in the queue.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
11 queue = deque([(root, None)]) # (node, parent)
12 x_info = y_info = None
13
14 while queue:
15 level_length = len(queue)
16 for i in range(level_length):
17 node, parent = queue.popleft()
18
19 if node.val == x:
20 x_info = (node, parent)
21 elif node.val == y:
22 y_info = (node, parent)
23
24 if x_info and y_info:
25 break
26
27 if node.left:
28 queue.append((node.left, node))
29 if node.right:
30 queue.append((node.right, node))
31
32 if x_info and y_info:
33 # Check if they are cousins (same depth but different parents)
34 return x_info[1] != y_info[1]
35 if x_info or y_info:
36 # Found one node but not the other in the same level
37 return False
38
39 return False
40In this Python solution, we use a deque to facilitate a level-order traversal. We track both the parent and depth of each node and check if the target nodes are at the same depth but have different parents. If they do, they are cousins.
This approach uses a DFS to recursively track the parent and depth of each node. On finding nodes x and y, checks are done whether they meet cousin criteria (same depth and different parents).
Time Complexity: O(n) where n is the total nodes count due to entire tree traversal.
Space Complexity: O(h) with h as the height of the tree, due to recursive stack space usage.
1class TreeNode:
2 def
This Python implementation uses DFS to recursively find the depth and parents of x and y. When both found, checks are done to validate if they are cousins by comparing depth and parent values.