Побудувати деревовидну структуру зі списку · fullstack.org.ua

Побудувати деревовидну структуру зі списку

ПросунутийReact

Перетворіть плаский список елементів із parentId на вкладене дерево.

Напишіть функцію solve(items), яка приймає плаский масив об'єктів виду { id, parentId, ...rest } (де parentId дорівнює null для кореневих елементів) і повертає масив кореневих елементів, у кожного з яких є поле children — масив його дочірніх елементів, побудований рекурсивно на будь-яку глибину. Типова задача при рендерингу вкладених коментарів, меню чи дерева категорій у React-застосунку.

Приклади

Вхід: [{ id: 1, parentId: null, name: "Root" }, { id: 2, parentId: 1, name: "Child" }]

Вихід: [{ id: 1, parentId: null, name: "Root", children: [{ id: 2, parentId: 1, name: "Child", children: [] }] }]

Вхід: []

Вихід: []

Обмеження: Кожен id унікальний; parentId (якщо не null) обов'язково посилається на існуючий id у тому самому масиві.

Ваше рішення

Підказки

Підказка 1

Спершу створіть довідник (об'єкт) id → елемент із додатковим порожнім масивом children — це дозволяє звертатись до будь-якого елемента за id за O(1).

Підказка 2

Другим проходом по items додайте кожен елемент у children його батька (за parentId) або, якщо parentId дорівнює null, — у масив коренів.

Пояснення розв'язку

javascript

function solve(items) {
  const byId = {};
  for (const item of items) {
    byId[item.id] = { ...item, children: [] };
  }

  const roots = [];
  for (const item of items) {
    const node = byId[item.id];
    if (item.parentId == null) {
      roots.push(node);
    } else {
      byId[item.parentId].children.push(node);
    }
  }

  return roots;
}