-1

我有一个经典的树问题，找不到正确的解决方案。我在 python 字典中有一棵树，上面有树枝和叶子。我需要计算每个分支的所有子项（价格属性）的总和并将其存储在总和属性中。这是我的树（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
                    }
                ]
            }
        ]
    }
]

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

谢谢你的帮助！

4

2 回答 2

0

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

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

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

于 2018-02-12T16:30:50.927 回答
0

您可以尝试按照以下方式进行排序：

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
于 2018-02-12T16:31:43.923 回答