Задача
Есть дерево, на котором сидят белки (squirrels) и вороны (ravens). Необходимо написать функцию, которая находит всех белок на дереве и возвращает их имена.
Пример
/**
* Type Tree = {
* nest: Squirrel | Raven;
* branches: Tree[];
* }
* Type Squirrel = {
* name: string;
* type: 'squirrel';
* }
* Type Raven = {
* name: string;
* type: 'raven';
* }
*/
const tree = {
nest: { name: 'NEVERMORE!', type: 'raven' },
branches: [
{
nest: { name: 'Acorn', type: 'squirrel' },
branches: [
{ nest: { name: 'Sir Salty', type: 'squirrel' } },
{
nest: { name: 'Huginn', type: 'raven' },
branches: [
{ nest: { name: 'Muninn', type: 'raven' } },
{ nest: { name: 'Kernel', type: 'squirrel' } },
],
},
],
},
{
nest: { name: 'Gvilum', type: 'raven' },
branches: [
{
nest: { name: 'Macadamia', type: 'squirrel' },
branches: [{ nest: { name: 'Boldric', type: 'raven' } }],
},
],
},
],
};Решение
Оптимальное решение
function squirrelScanner(tree) { const stack = [tree]; const requiredType = 'squirrel'; const names = []; while (stack.length > 0) { const node = stack.pop(); if (node.nest.type === requiredType) { names.push(node.nest.name); } if (node.branches?.length) { stack.push(...node.branches); } } return names; }