php中树数组中所有节点的总和值

Question

我有平面阵列像：

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

要求：

• 将平面数组转换为 树形数组 --> (DONE)
• 每个id的总和是它和它的孩子的总价

现在问题出现了：

• 应该在before或after从平面数组转换为树数组

这是我的代码，尝试将平面转换为树：

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,
                    },

我想知道是否可以在 buildTree 中处理求和？

我的想法是拥有一棵树，然后处理子级别的总和，但我无法处理将总和分配给父元素

Answer 1

我创建了一个班级并采纳了你的想法。

class TreeBuilder {
    private $flatArr;
    private $idToNode;

    public function __construct($flatArr) {
        // Keep the flat arr in case we need it.
        $this->flatArr = $flatArr;
        // Create an array to lookup a node to determine if it exists.
        $this->idToNode = array_combine(array_column($flatArr, 'id'), $flatArr);
    }

    public function buildTree() {
        // create an empty array to hold root nodes
        $roots = [];
        // iterate through each node and add it to its parent's children list
        foreach ($this->flatArr as &$node) {
            $id = $node['id'];
            $parentId = $node['parentId'];
            if (isset($this->idToNode[$parentId])) {
                $this->out("add child to $parentId " . print_r($node, true));
                $parentNode = &$this->idToNode[$parentId];
                if ( isset($parentNode['children']) ) {
                    $parentNode['children'] = [&$this->idToNode[$id]];
                } else {
                    $parentNode['children'][] = &$this->idToNode[$id];
                }
                // $children[] = &$node;
            } else {
                $this->out("add to root " . print_r($node, true));
                $roots[] = &$this->idToNode[$id];
            }
        }
        // calculate the sum of each node and its children recursively
        foreach ($roots as &$root) {
            $this->calculateSum($root);
        }
        return $roots;
    }

    private function calculateSum(&$node) {
        // calculate the sum of the current node
        $node['sum'] = $node['cost'];
        // recursively calculate the sum of the children nodes
        $children = &$node['children'];
        if (isset($children)) {
            foreach ($children as &$child) {
                $node['sum'] += $this->calculateSum($child);
            }
        }
        return $node['sum'];
    }

    private function out($s) {
        echo "$s\n";
    }
}