本文介绍一种递归算法，将“自底向上”的 parent 嵌套结构（如 ['name' => 'X', 'parent' => [...]]）转换为“自顶向下”的 child 嵌套结构（如 ['name' => 'X', 'child' => [...]]），适用于树形数据的逆向重构。

本文介绍一种递归算法，将“自底向上”的 parent 嵌套结构（如 `['name' => 'x', 'parent' => [...]]`）转换为“自顶向下”的 child 嵌套结构（如 `['name' => 'x', 'child' => [...]]`），适用于树形数据的逆向重构。

在实际开发中，我们常遇到树形数据以“反向链表”形式存储：每个节点仅持有对父节点（parent）的引用，而根节点的 parent 为 null。例如，表示三代继承关系的结构：

$demo = [
    'name' => 'name 3',
    'parent' => [
        'name' => 'name 2',
        'parent' => [
            'name' => 'name 1',
            'parent' => null
        ]
    ]
];

但业务逻辑（如渲染层级菜单、构建 DOM 树或序列化为 JSON API）往往需要正向结构——即每个节点通过 child 指向其直接子节点。目标结构如下：

$mirror = [
    'name' => 'name 1',
    'child' => [
        'name' => 'name 2',
        'child' => [
            'name' => 'name 3',
            'child' => null
        ]
    ]
];

实现的关键在于深度优先遍历到底层（parent === null），再逐层回溯组装 child 链。以下是一个健壮、类型安全的递归函数：

function mirror(?array $array, array $subArray = []): array
{
    // 终止条件：到达原始结构的根（即最年长节点），此时 parent 为 null
    if ($array === null) {
        return $subArray;
    }

    $name = $array['name'] ?? '';
    $parent = $array['parent'] ?? null;

    // 初始调用：尚未构建任何子结构，先创建最深层节点（即最终的根节点）
    if (empty($subArray)) {
        return mirror($parent, [
            'name' => $name,
            'child' => null
        ]);
    }

    // 回溯时：将当前节点作为新父节点，原已构建的子结构作为其 child
    return mirror($parent, [
        'name' => $name,
        'child' => $subArray
    ]);
}

✅ 使用示例：

$result = mirror($demo);
print_r($result);
// 输出即为目标 $mirror 结构

⚠️ 注意事项：

• 函数假设输入数组严格遵循 'name' 和 'parent' 键约定；建议在生产环境增加键存在性校验（如 isset($array['name'])）；
• 若原始结构存在环引用（如 A → B → A），会导致无限递归，应提前做循环检测；
• 对于超深嵌套（>1000 层），PHP 可能触发栈溢出，此时可考虑改用迭代+显式栈方式实现；
• 返回结构中 child 始终为 array|null，语义清晰，便于后续 JSON 序列化或前端消费。

该算法时间复杂度为 O(n)（n 为节点总数），空间复杂度也为 O(n)（递归调用栈深度 + 构建的新结构），是处理此类“链路翻转”问题的标准且高效解法。