Задача: массив в дерево и обратно
На этой странице
Частая практическая задача: сервер присылает плоский список с parentId (категории, комментарии, оргструктура, файлы), а интерфейсу нужно дерево. Решение за O(n): первым проходом положить все узлы в Map по id, вторым — добавить каждый узел в children родителя (или в корни, если родителя нет). Обратная задача — развернуть дерево в плоский список обходом в глубину. Продолжения: поиск узла, путь до узла (хлебные крошки), подсчет вложенности.
Вопрос
Преобразуйте массив { id, parentId, name } в дерево с children за O(n). Затем напишите обратное преобразование и функцию поиска пути до узла.
Плоский список → дерево
function arrayToTree(items) {
const byId = new Map();
const roots = [];
for (const item of items) {
byId.set(item.id, { ...item, children: [] }); // копируем, не мутируем вход
}
for (const item of items) {
const node = byId.get(item.id);
const parent = item.parentId == null ? null : byId.get(item.parentId);
if (parent) parent.children.push(node);
else roots.push(node); // корень или «сирота» без родителя в списке
}
return roots;
}const categories = [
{ id: 1, parentId: null, name: "Электроника" },
{ id: 2, parentId: 1, name: "Телефоны" },
{ id: 3, parentId: 1, name: "Ноутбуки" },
{ id: 4, parentId: 2, name: "Смартфоны" },
{ id: 5, parentId: null, name: "Книги" },
];
arrayToTree(categories);
// [
// { id: 1, name: "Электроника", children: [
// { id: 2, name: "Телефоны", children: [{ id: 4, name: "Смартфоны", children: [] }] },
// { id: 3, name: "Ноутбуки", children: [] } ] },
// { id: 5, name: "Книги", children: [] }
// ]Два прохода нужны, чтобы порядок элементов не имел значения: ребенок может стоять в массиве раньше родителя.
Дерево → плоский список
function treeToArray(nodes, parentId = null, depth = 0, result = []) {
for (const { children = [], ...rest } of nodes) {
result.push({ ...rest, parentId, depth });
treeToArray(children, rest.id, depth + 1, result);
}
return result;
}Поле depth удобно для отрисовки отступов в плоском списке или виртуализированном дереве.
Путь до узла (хлебные крошки)
function findPath(nodes, targetId, path = []) {
for (const node of nodes) {
const nextPath = [...path, node];
if (node.id === targetId) return nextPath;
const found = findPath(node.children ?? [], targetId, nextPath);
if (found) return found;
}
return null;
}
findPath(arrayToTree(categories), 4).map((n) => n.name);
// ["Электроника", "Телефоны", "Смартфоны"]С Map по id и parentId путь можно найти без обхода — поднимаясь от узла к корню за O(глубина).
Рендер дерева в React
function Tree({ nodes }) {
return (
<ul role="tree">
{nodes.map((node) => <TreeItem key={node.id} node={node} />)}
</ul>
);
}
function TreeItem({ node }) {
const [open, setOpen] = useState(false);
const hasChildren = node.children.length > 0;
return (
<li role="treeitem" aria-expanded={hasChildren ? open : undefined}>
{hasChildren ? <button onClick={() => setOpen(!open)}>{node.name}</button> : node.name}
{open && hasChildren && (
<ul role="group">
{node.children.map((child) => <TreeItem key={child.id} node={child} />)}
</ul>
)}
</li>
);
}Доп. вопросы интервьюера
- Сложность наивного решения? поиск родителя через
findдля каждого элемента — O(n²); сMap— O(n). - Как обнаружить цикл (
a.parentId = b,b.parentId = a)? при подъеме к корню хранить посещенные id. - Что делать с «сиротами»? зависит от задачи: в корни, отдельный список или ошибка.
- Очень глубокое дерево? итеративный обход со стеком вместо рекурсии.
Что важно помнить
- Не мутируйте входные объекты — создавайте копии с
children. parentId == nullловит иnull, иundefined.- Для больших деревьев в UI — ленивое раскрытие и виртуализация плоского списка с
depth. - Теория: tree, DFS и BFS для дерева.
Мини-шпаргалка
Список → дерево: проход 1 — Map id → { ...item, children: [] }, проход 2 — в children родителя или в roots. O(n). Дерево → список: DFS с parentId и depth. Путь: рекурсия с накоплением path. Не мутировать вход, учитывать сирот и циклы.