Сложность: easy
Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.
Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.
Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.
Пример:
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
👨💻 Алгоритм:
1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.
2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.
3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.
😎 Решение:
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:
parent_x, parent_y = None, None
depth_x, depth_y = -1, -1
def dfs(node, parent, depth):
nonlocal parent_x, parent_y, depth_x, depth_y
if not node:
return
if node.val == x:
parent_x, depth_x = parent, depth
elif node.val == y:
parent_y, depth_y = parent, depth
else:
dfs(node.left, node, depth + 1)
dfs(node.right, node, depth + 1)
dfs(root, None, 0)
return depth_x == depth_y and parent_x != parent_y
Ставь 👍 и забирай 📚 Базу знаний