如何使用Javascript计算一般树中children的总和

Question

我想计算 child 个节点的总和并将其保存在 parent 个节点上。如图所示，蓝色数字是 children 的总和。

到目前为止我已经试过了：

    const tree = {
          name:"Root Node",
          value:0,
          sumOfTheChildren:0,
          children: [
              {

                 name:"A Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              },

              {

                 name:"B Node",
                 value:10,
                 sumOfTheChildren:0,
                 children:[]
              }

    ]

    }

and so on ....

所以在每个节点的 sumOfTheChildren 中，我想计算 children（所有后代节点）

的总和

所以我正在尝试这样做 post-order tree traversal。

let sum = 0;
function postOrder(root) {
  if (root == null) return;

  root.children.forEach((el) =>{
     postOrder(el);

  });

  sum+=root.value;

  // Here i am not sure how to do this 
  root.sumOfTheChildren+=root.value;

}

postOrder(tree);

但这并没有给出所需的结果。那么我如何获得适当的金额？

Answer 1

可以简化逻辑，先递归计算children的和，然后返回children值和parents值的和。

const tree = {
  name: "Root Node",
  value: 0,
  sumOfTheChildren: 0,
  children: [{

      name: "A Node",
      value: 10,
      sumOfTheChildren: 0,
      children: [{

        name: "D Node",
        value: 35,
        sumOfTheChildren: 0,
        children: []
      }]
    },

    {

      name: "B Node",
      value: 10,
      sumOfTheChildren: 0,
      children: []
    }

  ]
};

function postOrder(root) {
  if (root.children) {
    root.children.forEach(child => {
      root.sumOfTheChildren += postOrder(child);
    });
  }

  return root.sumOfTheChildren + root.value;
}

console.log(postOrder(tree));
console.log(tree);

如何使用Javascript计算一般树中children的总和

How to calculate the sum of the children in a general tree using Javascript

javascript

algorithm

tree

depth-first-search