字典中的递归求和

Question

我有一个经典的树问题，找不到正确的解决方案。我有一棵树，在 python 字典中有树枝和树叶。我需要计算每个分支的所有 children (price-property) 的总和并将其存储在 sum-property 中。这是我的树 (dict) 的示例：

[
    {
        "id": 1,
        "type": "group",
        "name": "test-group 1",
        "price": 0,
        "sum": 0,
        "children": [
            {
                "id": 2,
                "type": "position",
                "name": "test-inner 1",
                "price": 5
            },
            {
                "id": 3,
                "type": "position",
                "name": "test-inner 2",
                "price": 10
            }
        ]
    },
    {
        "id": 4,
        "type": "group",
        "name": "test-group 2",
        "sum": 0,
        "children": [
            {
                "id": 5,
                "type": "position",
                "name": "test-inner 3",
                "price": 5
            },
            {
                "id": 6,
                "type": "group",
                "name": "test-group 3",
                "sum": 0,
                "children": [
                    {
                        "id": 7,
                        "type": "position",
                        "name": "test-inner 4",
                        "price": 5
                    },
                    {
                        "id": 8,
                        "type": "position",
                        "name": "test-inner 5",
                        "price": 10
                    }
                ]
            }
        ]
    }
]

我确定我需要递归并且已经找到解决方案来获得整棵树的总和...但我也需要部分总和...

感谢您的帮助！

Answer 1

假设非叶节点没有价格，这样做：

def add_sums(tree):
  if 'price' in tree:
    return tree['price']
  s = sum(map(add_sums, tree['children']))
  tree['sum'] = s
  return s

如果他们确实需要能够有价格，正如您的测试数据可能表明的那样，那么您可以这样做

def add_sums(tree):
  if 'children' not in tree:
      return tree['price']
  s = sum(map(add_sums, tree['children']))
  if 'price' in tree:
     s += tree['price']
  tree['sum'] = s
  return s

可能将节点价格的加法移动到更新总和之后，如果它应该只是子节点的总和。

Answer 2

您可以尝试以下几行：

def dct_sum(dct):
    if isinstance(dct, dict):
        if 'price' in dct:
            return dct['price']
        if 'children' in dct:
            dct['sum'] = sum(dct_sum(c) for c in dct['children'])
            return dct['sum']
    if isinstance(dct, list):
        return sum(dct_sum(item) for item in dct)
    return 0

字典中的递归求和

Recursive sums in dictionary

python

recursion

tree-structure