Дерево файлов: родитель объявлен позже
Условие
Список узлов [{ id, name, type, parentId }] превращается в дерево. Текущая реализация теряет связь, если родитель идёт в списке после ребёнка. Почини: порядок узлов в списке не должен иметь значения. Верни массив корневых узлов; у каждого поле children.
Что проверяют тесты
родители после детей
несколько корней
порядок детей сохраняется
вложение в файл запрещено
пустой список
Как подойти
Классический баг «зависит от порядка входных данных». Лечится разделением на две фазы: сначала создаём все узлы в словаре по id, потом проходим второй раз и связываем. Так порядок перестаёт иметь значение, и сложность остаётся линейной. Проверка parentId != null вместо if (parentId) важна: идентификатор ноль - валидный и при проверке на истинность узел ошибочно станет корневым.
Подсказки: 3
- Проблема в том, что связь строится в один проход, а родителя может ещё не быть.
- Два прохода: сначала создать все узлы, потом связать.
- parentId может быть нулём - проверяй на null и undefined, а не на истинность.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.