树遍历，退出最终递归时传递的变量重置为0(Javascript)

Question

谁能给我解释一下为什么给出这段代码来遍历二叉树：

var sumOfLeftLeaves = function(root) {
    let sum = 0;
    traverse(root, sum);
    return sum;
};


function traverse(root, sum) {

    const left = root.left;
    const right = root.right;


    if (left) {
        sum += left.val;
        traverse(left, sum);
    }

    if (right) {
        traverse(right, sum);
    }

}

在树的遍历过程中正确计算出的和，在退出最后一个递归阶段后重置为0？

Answer 1

您不会从 traverse 返回 sum，也不会在 sumOfLeftLeaves 中重新分配它。你可能想要更多这样的东西：

var sumOfLeftLeaves = function(root) {
    return traverse(root, 0);
};


function traverse(root, sum) {
    const left = root.left;
    const right = root.right;

    if (left) {
        sum += left.val;
        return traverse(left, sum);
    }

    if (right) {
        return traverse(right, sum);
    }

    return sum;
}

Answer 2

var sumOfLeftLeaves = function(root) {
    let sum = 0;
    return traverse(root, sum);
};


function traverse(root, sum) {

    const left = root.left;
    const right = root.right;

    sum += root.val
    if (left) {
        sum += traverse(left, sum);
    }

    if (right) {
        sum += traverse(right, sum);
    }
    return sum

}

sum 是一个不可变的值。这意味着每次将它作为参数传递给函数调用时，都会生成一个新副本。因此，您在递归堆栈下方所做的添加不会反映在上面堆栈帧中的 sum 变量中。

进一步阐述，sum是一个整数，在JS术语中是Number。它是一种值类型，这意味着在每次赋值时，它都是按值传递、复制的。换句话说，JS 运行时在堆栈上创建一个新位置并将分配的值存储在新位置。您对值类型所做的任何 mutation/modification 都不会反映在原始变量上。

这种方法解决了问题。

另一种方法是删除 sum 作为参数，只删除 return 节点值的总和，如下所示：

var sumOfLeftLeaves = function(root) {
    return traverse(root);
};


function traverse(root) {
    if (root == null) return 0

    return root.val + traverse(root.left) + traverse(root.right);
}

为了完整起见，第三种方法是使 sum 成为可变变量，例如 js 对象类型或数组。虽然对象或数组的结构本身是按值传递的，但它们的内容可以更改，并且这些更改将反映在原始变量中。假设您将 sum 作为一个元素 const sum = [0] 的数组传递。每当您向其中添加内容时，sum[0] += node.val，sum 索引零处元素的值都会发生变化，并且对于调用堆栈上方的函数也是可见的。

Answer 3

您可以采用单个函数，该函数 returns 值加上左侧和右侧或零。

const
    sumOfTree = node => node
        ? value + sumOfTree(node.left) + sumOfTree(node.right)
        : 0;

另一种解决方案可能是使用一个遍历函数，该函数接受一个节点和一个对对象进行闭包的函数作为值。

const
    traverse = (node, fn) => {
        if (!node) return;
        fn(node);
        traverse(node.left, fn);
        traverse(node.right, fn);
    },
    sumOfTree = result => node => result.sum += node.value;

// call
const
    result = { sum: 0 },
    getSum = sumOfTree(result);

traverse(tree, getSum);
console.log(result.sum);

树遍历，退出最终递归时传递的变量重置为0(Javascript)

Tree traversal, passed variable is reset to 0 when exiting the final recursion (Javascript)

javascript

algorithm

recursion

binary-tree