如何使用尾递归来优化这个算法？

Question

我想用尾递归来优化这个dfs，但我不知道如何实现它，有人可以帮助我吗？

我的第一个解决方案是以下代码，我想用尾递归修改它以获得 21 的测试用例

const tree = {
  val: 1,
  children: [
    { val: 2, children: [] },
    {
      val: 3,
      children: [
        { val: 4, children: [] },
        { val: 5, children: [] },
      ],
    },
    { val: 6, children: [] },
  ],
};


function dfs(root) {
  if (root.children && root.children.length > 0) {
    let tmp = 0;
    for (let i = 0; i < root.children.length; i++) {
      tmp += dfs(root.children[i]);
    }
    return (tmp += root.val);
  } else {
    return root.val;
  }
}

let ret = 0;
console.log("ret: ", dfs(tree));//get 21 this case

Answer 1

可以使用reduce方法和箭头函数来优化。

function dfs(root) {
   return root.val + root.children.reduce((sum, child) => sum + dfs(child), 0);
}