I want to optimize this dfs with tail recursion,but i don't konw how to realize it, could any help me?
My first solution is the following code, i want modify it with tail recursion to get test case with 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
DFS doesn't play nicely with tail recursion. You can hack around that, for example, by passing an explicit list of "nodes-to-visit", as in
function sum(todo, total=0) {
if (todo.length === 0)
return total
let [node, ...rest] = todo
return sum([...rest, ...node.children], total + node.val)
}
//
const tree = {
val: 1,
children: [
{ val: 2, children: [] },
{
val: 3,
children: [
{ val: 4, children: [] },
{ val: 5, children: [] },
],
},
{ val: 6, children: [] },
],
};
let ret = 0;
console.log("ret: ", sum([tree])); //get 21 this case
...but that hardly counts as an "optimization".