Конверсия плоского массива в вложенную иерархию дерева

Условие

Дан линейный набор элементов, представляющих узлы дерева. Каждый элемент содержит уникальный идентификатор id и ссылку на родительский узел parent, которая может быть null (корневой узел) либо указывать на id другого элемента. Требуется собрать полное дерево произвольной глубины, разместив дочерние элементы внутри массива children их родителя.

/**
 * @param array{int, array{id: int, name: string, parent: ?int}} $flatList
 *
 * @return array{int, array{id: int, name: string, parent: ?int, children: array{int, array}}}
 */
function mapTree(array $flatList): array
{
    // implement conversion here
}

function testBuildTree(): void
{
    $source = [
        0 => ['id' => 0, 'parent' => null], // корень
        1 => ['id' => 1, 'parent' => null], // корень
        2 => ['id' => 2, 'parent' => 1],    // потомок 1
        3 => ['id' => 3, 'parent' => 1],    // потомок 2
        4 => ['id' => 4, 'parent' => 2],    // внук 1
        5 => ['id' => 5, 'parent' => 4],    // правнук 1
    ];

    $resultTree = [
        0 => ['id' => 0, 'parent' => null],
        1 => [
            'id' => 1, 'parent' => null, 'children' => [
                0 => ['id' => 2, 'parent' => 1, 'children' => [
                    0 => ['id' => 4, 'parent' => 2, 'children' => [
                        0 => ['id' => 5, 'parent' => 4],
                    ]],
                ]],
                1 => ['id' => 3, 'parent' => 1],
            ],
        ],
    ];

    assert(mapTree($source) === $resultTree);
}

testBuildTree();

Ответ

Сначала сгруппируйте узлы по parent, затем рекурсивно соберите ветви от корней. Чтобы совпасть с примером, добавляйте children только непустым узлам.

function mapTree(array $flatList): array {
    $children = [];
    foreach ($flatList as $item) {
        $key = $item['parent'] === null ? 'root' : 'id:' . $item['parent'];
        $children[$key][] = $item;
    }
    $build = function (string $key) use (&$build, $children): array {
        $result = [];
        foreach ($children[$key] ?? [] as $item) {
            $nested = $build('id:' . $item['id']);
            if ($nested !== []) $item['children'] = $nested;
            $result[] = $item;
        }
        return $result;
    };
    return $build('root');
}

Предполагаются уникальные ID, существующие родители и отсутствие циклов. Для внешних данных эти условия проверяют до сборки, иначе потеряются недостижимые узлы. Группировка даёт O(n) обходов узлов.