Сегодня мы собираемся решить ту же задачу о деревьях, где вам даны два бинарных дерева, и мы должны сравнить их и посмотреть, идентичны ли они или нет.
Имея корни двух бинарных деревьев p и q, напишите функцию, проверяющую, совпадают ли они или нет.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.
Input: p = [1,2,3], q = [1,2,3] Output: true
Input: p = [1,2,1], q = [1,1,2]
Output: false
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
elif p is None or q is None:
return False
elif p.val != q.val:
return False
else:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Пояснение :-
Эта функция использует рекурсию, чтобы проверить, совпадают ли два заданных бинарных дерева. В базовом случае оба параметра p и q равны None, и в этом случае функция возвращает значение True. Если только одно из них равно None, функция возвращает False, так как они не совпадают. Если значения корней p и q не совпадают, функция также возвращает False. Если ни один из этих случаев не соответствует действительности, функция рекурсивно проверяет левое и правое поддеревья p и q. Если и левое, и правое поддеревья совпадают, функция возвращает True, в противном случае — False.
Вы также можете реализовать это с помощью итерации с помощью очереди, где вы будете добавлять узлы обоих деревьев и сравнивать, совпадают ли значение и левый и правый узлы или нет.
Какова его временная и пространственная сложность?
Временная сложность этой реализации равна O(n), где n – количество узлов в дереве. Это связано с тем, что каждый узел в дереве посещается ровно один раз. Пространственная сложность также равна O(n), потому что в худшем случае нам нужно сохранить n узлов в стеке вызовов во время рекурсии.
В случае реализации итерации временная сложность по-прежнему будет O(n), так как мы посещаем каждый узел один раз, а пространственная сложность будет равна O(min(n,m)), где n и m — количество узлов. в первом и втором дереве соответственно.
Стоит отметить, что если деревья не сбалансированы, временная сложность будет хуже, чем O (n), из-за количества вызовов рекурсии, которые будет выполнять алгоритм.
Кроме того, при очень глубоком дереве лучше использовать рекурсию, а не итерацию, поскольку рекурсия занимает меньше места в памяти для стека вызовов.
Вы проверяете мой репозиторий Github для других проблем здесь: -
Удачного кодирования :)
