javascript - 在 Javascript 中对子值求和并将结果保存到 n 叉树中的父值

Question

我有一个 Javascript 树，结构如下，一个简单的例子:

tree: [
    {
      id: 'A'
      parents: []
      children: ['B']
      value: 1
    },
    {
      id: 'B'
      parents: ['A']
      children: ['C', 'D']
      value: 1
    },
    {
      id: 'C'
      parents: ['B']
      children: []
      value: 1
    },
    {
      id: 'D'
      parents: ['B']
      children: []
      value: 1
    }
]

      A
      |
      B
     / \
    C   D

每个节点都可以有不固定数量的子节点，我使用父数组来了解树根(当父数组为空时)。

我想做的是一个递归函数:子值的总和保存在父值中(覆盖值)。如果只有一个子项，则子值保存在父项中。因此，值会累积到根。

树结构好吗？如何实现该功能？

谢谢。

编辑:

预期结果:

tree: [
        {
          id: 'A'
          parents: []
          children: ['B']
          value: 2
        },
        {
          id: 'B'
          parents: ['A']
          children: ['C', 'D']
          value: 2
        },
        {
          id: 'C'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'D'
          parents: ['B']
          children: []
          value: 1
        }
    ]

另一个例子:

       A
     /   \
    B     E
   / \    |
  C   D   F

所有节点值 = 1。

预期结果:

tree: [
        {
          id: 'A'
          parents: []
          children: ['B','E']
          value: 3
        },
        {
          id: 'B'
          parents: ['A']
          children: ['C', 'D']
          value: 2
        },
        {
          id: 'C'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'D'
          parents: ['B']
          children: []
          value: 1
        },
        {
          id: 'E'
          parents: ['A']
          children: ['F']
          value: 1
        },
        {
          id: 'F'
          parents: ['E']
          children: []
          value: 1
        }
    ]

A值=B值+E值。

B值=C值+D值

E值=F值。

Answer 1

请注意，树结构与您的不同，但如果需要，您也可以插入其他属性(例如id)。

const tree = {
    value: 1,
    children: [{
        value: 1,
        children: [{
            value: 1,
            children: null
        },
        {
            value: 1,
            children: null
        }]
    }]
};

function sum(node) {
    var childSum = 0;
    if (!node.children) return node.value;
    for (var i = 0; i < node.children.length; i++) {
        childSum += sum(node.children[i]);
    }
    node.value = childSum;
    return childSum;
}

sum(tree);