re:re:actable
Урок 034 минуты чтения

Задача: массив в дерево и обратно

На этой странице
Кратко

Частая практическая задача: сервер присылает плоский список с 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. Не мутировать вход, учитывать сирот и циклы.

Документация

MDN: Map, W3C APG: Tree View Pattern, MDN: Recursion.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам