Сегодня мы будем работать над популярным вопросом, который задают на технических собеседованиях в компаниях MAANG и других компаниях.
Учитывая root
бинарного дерева, вернуть его максимальную глубину.
Максимальная глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего конечного узла.
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def find_depth(root): if root is None: return 0 left_depth = find_depth(root.left) right_depth = find_depth(root.right) return max(left_depth, right_depth) + 1 root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Depth of the tree:", find_depth(root)) #output is 3
Эта программа определяет класс Node
с атрибутом data
, а также атрибутами left
и right
, представляющими его левый и правый потомки соответственно. Функция find_depth
принимает узел root
и рекурсивно обходит дерево, возвращая максимальную глубину левого и правого поддеревьев +1 для каждого узла. Функция вызывается для определенного дерева с корнем root
, и выводится глубина дерева.
Стоит отметить, что глубина дерева — это длина самого длинного пути от корня до конечного узла. Эта функция использует рекурсию для обхода левого и правого поддеревьев, находит максимальную глубину обоих и возвращает максимальную глубину левого и правого поддеревьев +1, что дает глубину двоичного дерева.
Обратите внимание:-
Временная сложность приведенной выше программы составляет O(n), где n — количество узлов в двоичном дереве. Это связано с тем, что программа посещает каждый узел дерева ровно один раз.
Пространственная сложность приведенной выше программы составляет O(h), где h — высота двоичного дерева. Это связано с тем, что программа использует рекурсию, и каждый рекурсивный вызов добавляет новый кадр в стек вызовов. Поскольку максимальное количество фреймов, которые можно добавить в стек вызовов, равно высоте дерева, объемная сложность равна O(h).
https://github.com/klaus19 Следуйте за мной здесь, на GitHub, удачного кодирования :)