Как из вложенных массивов выбрать нужные элементы без рекурсии?

Question

[AlexAll]

Есть массив объектов:

[
    {
        "id": 1,
        "name": "Бумага",
        "children" :[
            {
                "id": 2,
                "name": "Бумага офисная",
                "children" :[
                    {
                        "id": 3,
                        "name": "Бумага для принтера"
                    },
                    {
                        "id": 4,
                        "name": "Бумага для цветная"
                    }
                ]

            }
        ]
    },
    {
        "id": 5,
        "name": "Товары для офиса",
        "children" :[
            {
                "id": 6,
                "name": "Оборудование",
                "children" :[
                    {
                        "id": 7,
                        "name": "Для досок"
                    },
                    {
                        "id": 8,
                        "name": "Бэйджики"
                    }
                ]

            }
        ]
    },
    {
        "id": 9,
        "name": "Товары для школы",
        "children" :[
            {
                "id": 10,
                "name": "Подарки",
                "children" :[
                    {
                        "id": 11,
                        "name": "Конфеты"
                    },
                    {
                        "id": 12,
                        "name": "Игрушки"
                    }
                ]

            }
        ]
    }
]

Нужно выбрать элементы без children, т.е.

[
		{
                        "id": 3,
                        "name": "Бумага для принтера"
                    },
                    {
                        "id": 4,
                        "name": "Бумага для цветная"
                    },
                                {
                        "id": 7,
                        "name": "Для досок"
                    },
                    {
                        "id": 8,
                        "name": "Бэйджики"
                    },
		{
                        "id": 11,
                        "name": "Конфеты"
                    },
                    {
                        "id": 12,
                        "name": "Игрушки"
                    }
]

Можно это сделать без рекурсии?

Comments

[Вадим]

можно, но не нужно

[AlexAll]

Вадим, ну покажите, для самообразования)

[Вадим]

AlexAll, для самообразования могу статью предложить
https://habr.com/ru/post/533034/
Не уверен что она на 100% релеванта, так сам не читал, но, бегло пробежавшись - где то рядом.

[AlexAll]

Вадим, Там в статье как я понял, говорится что рекурсия зло, на большую глубину js ходить не может

[Вадим]

AlexAll, ну да, только "Большая" это штука относительная и для Вашего примера эта глубина с вероятностью близкой к 100% - недостижима. То есть для Вашего примера в это ограничение Вы не упрётесь. Очень маловероятно что у Вас будет цепочка из вложенных объектов на несколько тысяч звеньев

[AlexAll]

Вадим, ну это то да))
Ладно спасибо больше там ниже пример циклах написали)))

Answer 1

[0xD34F]

function getLeaves(tree) {
  const result = [];

  for (const stack = [...tree]; stack.length;) {
    const n = stack.pop();
    if (Array.isArray(n.children) && n.children.length) {
      stack.push(...n.children);
    } else {
      result.push(n);
    }
  }

  return result.reverse();
}

или

function getLeaves(tree) {
  const result = [];
  const stack = [];

  for (let arr = tree, i = 0; i < arr.length || stack.length; i++) {
    if (i === arr.length) {
      [ i, arr ] = stack.pop();
    } else if (arr[i].children instanceof Array && arr[i].children.length) {
      stack.push([ i, arr ]);
      [ i, arr ] = [ -1, arr[i].children ];
    } else {
      result.push(arr[i]);
    }
  }

  return result;
}

или

function getLeaves([...tree]) {
  for (let i = 0; i < tree.length; i++) {
    const c = tree[i].children;
    if (c?.constructor === Array && c.length) {
      tree.splice(i--, 1, ...c);
    }
  }

  return tree;
}

Comments

[AlexAll]

Это будет работать если вложенность у объектов будет разная?

[0xD34F]

AlexAll, разрешаю вам проверить это самостоятельно.

[AlexAll]

0xD34F, Спасибо большое