Код Senior Деревья обновлено
Минимальная глубина дерева
Условие
Длина кратчайшего пути от корня до листа в рёбрах плюс один (число узлов). Узел с одним ребёнком листом не является.
Что проверяют тесты
лист близко
цепочка
один узел
пустое дерево
Как подойти
В отличие от максимальной глубины, здесь BFS выигрывает у DFS: он останавливается на первом же листе, не обходя глубокие ветки. Главная ловушка - определение листа: узел с одной веткой листом не является, и наивная рекурсия min(left, right) вернёт единицу для цепочки, потому что отсутствующая ветка даст ноль.
Подсказки: 2
- Обход в ширину находит ближайший лист и сразу останавливается.
- Узел с одним ребёнком - не лист, и его нельзя считать концом пути.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.