pro.algorithms
Может кто определить скррость и затрачиваемую этим алгоритмом память? Вроде
проход по всем нодам и потом еще на возврат это O(2n) | на память две переменные внутри функции это 2n + 1 или 3n? Сразу извиняюсь если фигню написал, просто не смыслю в этом. -- Надо найти ветвь минимальной длинны. Если одна из сторон null, то возвращаю максимальную длинну, потому что дальше ветви нет, если обе ветки ноды не равны нулю, получаю минимальное значение (одна из ветвей оказалась меньше другой)
6 ответов
Сладкий
Автор вопроса
Такое потреблением памяти может быть из-за того, что на стеке также хранится переменная n. Кажется, что без неё можно успешно обойтись
А в чем великий смысл передачи глубины вниз? Вы ведь не тейлрек пишите
Еще момент - в асимптотической сложности не существует сложности 3N, то есть константы-множители выносятся за скобки, и не учитываются. Если говорить о скорости поиска минимума, то этот алгоритм можно оптимизировать. Во-первых, не нужно передавать n. Во-вторых, вызывать рекурсию только для ненулевых элементов, соответственно, проверка на null root не нужна, но появятся проверки на null для потомков, как только потомок null - возвращаем 0. Если оба потомка не null, возвращаем 1 + Math.Min(depth(root.right), depth(root.left));
Ну и может оказаться, что поиск в глубину лучше заменить на поиск в ширину, то есть BFS, где нужно будет отслеживать глубину каждого узла, и опять же - останавливаться сразу, как найден кто-то с хотя бы одним отсутствующим потомком.
Сладкий
Автор вопроса
Похожие вопросы
Обсуждают сегодня