Есть дерево категорий интернет-магазина. Найдите категорию с заданным названием и
верните путь до неё от верхнего уровня — названия категорий по порядку, включая саму
найденную. Если категории нет, верните nil, false.
type Node struct {
Title string
Items []*Node
}
// FindPath возвращает путь от категории верхнего уровня до категории target.
func FindPath(categories []*Node, target string) ([]string, bool)
Пример
Электроника
├── Ноутбуки
│ ├── Игровые
│ ├── Ультрабуки
│ └── Бюджетные
├── Наушники
│ ├── Проводные
│ └── Беспроводные
└── Зарядки
Сад
├── Цветы
└── Инструменты
FindPath(categories, "Ультрабуки") → ["Электроника", "Ноутбуки", "Ультрабуки"], true
FindPath(categories, "Сад") → ["Сад"], true
FindPath(categories, "Посуда") → nil, false
Для вывода strings.Join(path, " > ") даёт Электроника > Ноутбуки > Ультрабуки.
Требования
- Если категорий с таким названием несколько, вернуть путь до первой в порядке
обхода в глубину (узел, затем его дети слева направо, корни слева направо).
- Как только категория найдена, обход прекращается.
- До 10⁶ узлов, глубина до 10⁵. O(n) времени.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.