129 lines
2.6 KiB
Markdown
129 lines
2.6 KiB
Markdown
---
|
|
layout: page
|
|
title: Cousins in Binary Tree
|
|
last_solved:
|
|
category: bfs/dfs
|
|
leetcode_url: https://leetcode.com/problems/cousins-in-binary-tree
|
|
status: Solved
|
|
---
|
|
|
|
Problem
|
|
-------
|
|
|
|
```
|
|
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
|
|
----------
|
|
|
|
BFS
|
|
|
|
{% highlight python %}
|
|
|
|
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
|
|
|
|
if not root:
|
|
return []
|
|
|
|
q = [root]
|
|
parents = defaultdict(list) # track parents in a dictionary
|
|
levels = []
|
|
|
|
|
|
parents[root.val] = None
|
|
|
|
while q:
|
|
|
|
level = []
|
|
|
|
for _ in range(len(q)):
|
|
|
|
curr = q.pop(0)
|
|
level.append(curr.val)
|
|
|
|
if curr.left:
|
|
q.append(curr.left)
|
|
parents[curr.left.val] = curr.val
|
|
|
|
|
|
if curr.right:
|
|
q.append(curr.right)
|
|
parents[curr.right.val] = curr.val
|
|
|
|
levels.append(level)
|
|
|
|
print(levels)
|
|
print(parents)
|
|
|
|
|
|
# loop thru rows and check if they have different parents
|
|
for row in levels:
|
|
if x in row and y in row and parents[x] != parents[y]:
|
|
return True
|
|
|
|
return False
|
|
|
|
{% endhighlight %}
|
|
|
|
______________
|
|
|
|
DFS
|
|
|
|
[How does this work with self](https://leetcode.com/problems/cousins-in-binary-tree/discuss/741717/Python-beats-98-(easy-to-understand)-with-explanation)
|
|
|
|
Note: use `self.xxx` instead of `nonlocal`
|
|
|
|
{% highlight python %}
|
|
|
|
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
|
|
|
|
def dfs(node, level, parent):
|
|
|
|
if not node:
|
|
return
|
|
|
|
if node.val == x:
|
|
self.x_level = level
|
|
self.x_parent = parent
|
|
elif node.val == y:
|
|
self.y_level = level
|
|
self.y_parent = parent
|
|
|
|
dfs(node.left, level+1, node)
|
|
dfs(node.right, level+1, node)
|
|
|
|
|
|
dfs(root, 0, None)
|
|
|
|
return self.x_level==self.y_level and self.x_parent!=self.y_parent
|
|
|
|
{% endhighlight %} |