Максимальный зигзагообразный путь в бинарном дереве

Продолжаем закреплять тему деревьев. В общем виде, если вы встречаете задачу на деревья или графы, с большой долей вероятности стоит вспоминать и модифицировать поиск в ширину/глубину.

Сложность: 🟡 Средняя

ℹ️ Описание

Напишите функцию, которая будет вычислять длину самого длинного зигзагообразного пути в бинарном дереве. Путь может начинаться НЕ с корневого элемента дерева.

⚠️ Ограничения

Количество элементов в дереве от 1 до 50000


✅ Решение

Для решение задачи нам потребуется вспомнить как работает алгоритм поиска в глубину и немного модифицировать его. Основная сложность данной задачи в том, что наш путь не обязан начинаться от корня дерева, он может «всплывать» из более глубоких слоев дерева, поэтому на каждой ноде нам нужно оперировать четырьмя величинами:

- Длиной пути, начинающегося от текущего элемента направо.
- Длиной пути, начинающегося от текущего элемента налево.
- Длиной максимального пути «снизу» с левой дочерней ноды.
- Длиной максимального пути «снизу» с правой дочерней ноды.

Поднимаясь по слоям дерева во время рекурсивного обхода нам будет достаточно вычислять и возвращать максимум из этих величин.

Посмотреть примеры и реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) —так как нам нужно совершить поиск в глубину по бинарному дереву, перебрав все n его элементов.

По памяти

O(n) — так как мы используем рекурсивный подход. Это означает, что мы будем хранить в памяти n переменных во время вычисления стека рекурсии.

#tries #medium