Сегодня мы будем работать над популярным вопросом, который задают на технических собеседованиях в компаниях 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, удачного кодирования :)