Как рассчитать сумму детей в общем дереве с помощью Javascript

введите описание изображения здесь

Я хочу вычислить сумму дочерних узлов и сохранить ее на родительском узле. Как показано на рисунке синие цифры - сумма детей.

Я пробовал это до сих пор:

    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 каждого узла я хочу вычислить сумму детей (все узлы-потомки)

поэтому я пытаюсь сделать 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);

Но это не дает требуемого результата. Итак, как мне получить правильную сумму?

Всего 1 ответ


Логика может быть упрощена путем рекурсивного вычисления сначала суммы детей, а затем возврата суммы значений детей и значения родителей.

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);


Есть идеи?

10000