递归不保留 javascript 中的值

Question

我目前正在尝试解决这个问题：https://leetcode.com/problems/maximum-depth-of-binary-tree/

这是我的代码：

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
 }
 
 const NINE = new TreeNode(9);
 const FIFTEEN = new TreeNode(15);
 const SEVEN = new TreeNode(7);
 const TWENTY = new TreeNode(20, FIFTEEN, SEVEN);
 const THREE = new TreeNode(3, NINE, TWENTY);


var maxDepth = function(root) {
    let max = 0;
    helper(root, max, 0);
    console.log(max, 'max')
    return max + 1;
};

function helper(root, max, i) {
    if(root === null) return max;
    if(max < i) {
        max = i;
     }
    
     const maxLeft = helper(root.left, max, i+1); 
     const maxRight = helper(root.right, max, i+1);
    
    return max = maxLeft > maxRight ? maxLeft : maxRight;
}

maxDepth(THREE);

有了这个，我有 3 个问题：

1) 我不明白这一行：

return max = maxLeft > maxRight ? maxLeft : maxRight; //2

这里，maxDepth函数中的max值不也更新了吗？这样的话，我觉得应该是2。但是，当我在原始函数中 console.logged 时，结果收到 0 。为什么会发生这种情况，我如何才能从调用堆栈中保留最大值 return？

原来我在下面写了这两行：

const maxLeft = helper(root.left, max, i+1); 
const maxRight = helper(root.right, max, i+1);

如：

helper(root.left, max, i+1); 
helper(root.right, max, i+1);

因为我的逻辑是在这个条件之后：

if(max < i) {
   max = i;
}

但是，似乎随着函数 return 到达调用堆栈，max 被设置回 0。为什么 max 的值不是保留，我们如何保留该值？

我仍然对上面的两行感到困惑：

const maxLeft = helper(root.left, max, i+1); //1
const maxRight = helper(root.right, max, i+1); //2

这里，maxLeft和maxRight的值被保留为1和2。当我们 return 调用堆栈时，为什么不将它们设置回 0？

Answer 1

当您将数字发送到函数并在函数内更改它时，它只会在该函数内更改 -

var maxDepth = function(root) {
    let max = 0;            // define a number, max
    helper(root, max, 0);   // call helper with root, max, and 0
    console.log(max, 'max') // max will always be 0, helper cannot change it
    return max + 1;         // this will always be 0 + 1
};

看到下面的helper里面有return的说法吗？这意味着 new 值即将出现。在上面的代码中，您什么都不做。它被简单地丢弃，执行移到下一行 -

function helper(root, max, i) {
    if(root === null) return max;
    if(max < i) {
        max = i;
     }
    
     const maxLeft = helper(root.left, max, i+1); 
     const maxRight = helper(root.right, max, i+1);
    
    return max = maxLeft > maxRight ? maxLeft : maxRight; // <-
}

因此您可以通过在 maxDepth -

中重新分配它来更新 max

var maxDepth = function(root) {
    let max = 0;
    max = helper(root, max, 0); // <- get new max from helper
    console.log(max, 'max')
    return max + 1;
};

这可能会解决您的一些误解，但遗憾的是它并没有解决代码问题。递归是一种函数式继承，因此将它与函数式风格一起使用会产生最好的结果。这意味着要避免诸如突变、变量重新分配和其他副作用之类的事情。

const empty =
  {}
 
const node = (val, left = empty, right = empty) =>
  ({ val, left, right })

function max(a, b)
{ if (a > b)
    return a
  else
    return b
}
 
function depth(t)
{ if (t === empty)
    return 0
  else
    return 1 + max(depth(t.left), depth(t.right))
}

const mytree = 
  node(3, node(9), node(20, node(15), node(7)))
  
console.log(depth(mytree))
// 3

递归不保留 javascript 中的值

Recursion is not preserving values in javascript

javascript

tree

recursion

binary-tree

callstack