PHP中Flat Array转Tree Array节点求和时机及buildTree内实现疑问

问题背景 #

我有如下结构的扁平数组：

[
    {
        "id": "1",
        "parentId": "0",
        "cost": 1000
    },
    {
        "id": "2",
        "parentId": "1",
        "cost": 2000
    },
    {
        "id": "3",
        "parentId": "2",
        "cost": 4000
    },
    ...
]

需求 #

• 将扁平数组转换为树形数组（已完成）
• 每个节点的sum值为自身cost与所有子节点sum值的总和

当前疑问 #

• 求和操作应在转树形数组之前还是之后执行？
• 是否可在现有buildTree函数内实现求和逻辑？

现有转树代码 #

public function buildTree(array $flat)
{
    $grouped = [];
    $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
        foreach ($companies as $k => $company) {
            $id = $company['id'];
            if (isset($grouped[$id])) {
                $company['children'] = $fnBuilder($grouped[$id]);
            }
            $companies[$k] = $company;
        }
        return $companies;
    };
    return $fnBuilder($grouped[0]);
}

期望结果示例 #

[
    {
        "id": "1",
        "sum": 7000,
        "children": [
            {
                "id": "2",
                "sum": 6000,
                "children": [
                    {
                        "id": "3",
                        "sum": 4000
                    }
                ]
            }
        ]
    }
]

我的思路是先建树再处理子级求和，但无法将求和结果赋值给父元素，寻求解决方案。

解答 #

关于求和时机与函数整合 #

求和操作更适合在构建树形结构的过程中同步完成，因为递归构建子节点时，我们可以先计算子节点的sum，再向上回溯计算父节点的sum，这样不需要额外遍历树结构，效率更高，也能自然解决父节点无法获取子节点求和结果的问题。而且完全可以在现有buildTree函数内整合求和逻辑。

修改后的代码实现 #

注意原代码里$grouped变量没有初始化，需要先把扁平数组按parentId分组，这一步是原代码缺失的部分，补上后再整合求和逻辑：

public function buildTree(array $flat)
{
    // 先把扁平数组按parentId分组，快速定位子节点
    $grouped = [];
    foreach ($flat as $item) {
        $parentId = $item['parentId'];
        if (!isset($grouped[$parentId])) {
            $grouped[$parentId] = [];
        }
        $grouped[$parentId][] = $item;
    }

    // 递归构建树并同步计算sum
    $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
        foreach ($companies as $k => $company) {
            $id = $company['id'];
            $children = [];
            // 递归处理子节点，先拿到子节点的sum结果
            if (isset($grouped[$id])) {
                $children = $fnBuilder($grouped[$id]);
            }
            
            // 计算当前节点sum：自身cost + 所有子节点sum之和
            $sum = $company['cost'];
            foreach ($children as $child) {
                $sum += $child['sum'];
            }
            
            // 组装节点数据，保留必要字段
            $companies[$k] = [
                'id' => $company['id'],
                'sum' => $sum,
                ...(!empty($children) ? ['children' => $children] : [])
            ];
        }
        return $companies;
    };

    // 从根节点（parentId为0）开始构建
    return $fnBuilder($grouped[0] ?? []);
}

代码说明 #

1. 分组初始化：遍历扁平数组按parentId分组，避免递归时重复遍历整个数组，提升效率。
2. 递归求和逻辑：先递归处理所有子节点，拿到子节点的sum后，再计算当前节点的sum——因为递归是从最底层节点开始计算，所以父节点能直接获取到子节点的最终求和结果，自然解决了父节点无法赋值的问题。
3. 节点组装：只保留需要的字段，没有子节点时可以省略children字段，也可以根据需求添加原数组中的其他字段。

替代方案：先建树再求和 #

如果坚持先构建完整树形结构再求和，也可以通过单独的递归函数实现：

// 先补全原buildTree的分组逻辑，构建完整树形结构
public function buildTree(array $flat)
{
    $grouped = [];
    foreach ($flat as $item) {
        $parentId = $item['parentId'];
        if (!isset($grouped[$parentId])) {
            $grouped[$parentId] = [];
        }
        $grouped[$parentId][] = $item;
    }

    $fnBuilder = function ($companies) use (&$fnBuilder, $grouped) {
        foreach ($companies as $k => $company) {
            $id = $company['id'];
            if (isset($grouped[$id])) {
                $company['children'] = $fnBuilder($grouped[$id]);
            }
            $companies[$k] = $company;
        }
        return $companies;
    };

    return $fnBuilder($grouped[0] ?? []);
}

// 递归遍历树形结构计算sum
public function calculateSum(&$tree)
{
    foreach ($tree as &$node) {
        $sum = $node['cost'];
        if (isset($node['children']) && !empty($node['children'])) {
            // 先递归计算子节点的sum
            $this->calculateSum($node['children']);
            // 累加子节点sum到当前节点
            foreach ($node['children'] as $child) {
                $sum += $child['sum'];
            }
        }
        $node['sum'] = $sum;
    }
}

// 使用方式
$tree = $this->buildTree($flatArray);
$this->calculateSum($tree);

这种方式逻辑更分离，但需要两次递归遍历，效率略低于同步处理的方案，适合对代码模块化要求更高的场景。

内容的提问来源于stack exchange，提问作者Nguyễn John