js проблема с созданием дерева

Question

Пытаюсь плоский массив трансформировать в дерево, но не правильно формируется, повторяются.

const arr = [
  { id: 1, name: "input1", parent: null },
  { id: 3, name: "input2", parent: "panel#1" },
  { id: 4, name: "panel#2", parent: "panel#1" },
  { id: 5, name: "input3", parent: "panel#2" },
  { id: 6, name: "panel#3", parent: null },
  { id: 7, name: "input4", parent: "panel#3" },
  { id: 2, name: "panel#1", parent: null },
];

let result = [];
function getTree(flatArr) {
  // должно быть отсортированно
  flatArr.sort(function (a, b) {
    return a.id - b.id;
  });

  flatArr.forEach((elem, index) => {
    result[index] = elem;
    if (elem.parent !== null) {
      recursive(elem.parent, index);
    }
  });

  function recursive(parrentName, index) {
    flatArr.forEach((elem) => {
      if (elem.name === parrentName) {
        result[index] = { ...elem, child: result[index] };
        if (elem.parent !== null) {
          recursive(elem.parent, index);
        }
      }
    });
  }
}

getTree(arr);

console.log(...result);

Answer 1

Это делается за O(n) без сортировок и рекурсий.

const arr = [
  { id: 1, name: "input1", parent: null },
  { id: 3, name: "input2", parent: "panel#1" },
  { id: 4, name: "panel#2", parent: "panel#1" },
  { id: 5, name: "input3", parent: "panel#2" },
  { id: 6, name: "panel#3", parent: null },
  { id: 7, name: "input4", parent: "panel#3" },
  { id: 2, name: "panel#1", parent: null }
];

function getTree(flatArr) {
  let arr = flatArr.map(i => ({...i}));
  let lookup = arr.reduce((r,i) => (r[i.name] = i, r), {});
  arr.forEach(i => {
    let parent = lookup[i.parent];
    if (parent) {
      (parent.children || (parent.children = [])).push(i);
    }
  });
  return arr.filter(i => !i.parent);
}

console.log(getTree(arr));

БЛОГ НА HUSL

js проблема с созданием дерева

Ответы (1 шт):