递归函数如何在搜索二叉树的最大深度时保持计数javascript

Question

 var maxDepth = function(root) {
     const recursion = (n) => {
         if (!n) return 0;
        
         let left = recursion(n.left)
         let right = recursion(n.right)
         return left > right ? left + 1 : right + 1
     }
     return recursion(root)
 };

调用递归函数时，如何保持计数？我见过很多其他方法来查找二叉树的最大深度，并且所有递归函数都自己计算。谁能解释一下这是如何工作的？函数调用加 1 是如何工作的？

这是另一种搜索方法

  maxDepth() {
    if (!this.root) return 0;

    function maxDepthHelper(node) {
      if (node.left === null && node.right === null) return 1;
      if (node.left === null) return maxDepthHelper(node.right) + 1;
      if (node.right === null) return maxDepthHelper(node.left) + 1;
      return (
        Math.max(maxDepthHelper(node.left), maxDepthHelper(node.right)) + 1
      );
    }

    return maxDepthHelper(this.root);
  }

这个是二叉树的一部分 class 方法

Answer 1

你问，“函数调用加 1 是如何工作的？”请注意 maxDepthHelper(...) return 是一个数字。所以，发生的事情是函数调用的 result 是一个数字，结果是递增 1。所以，如果在特定情况下 maxDepthHelper(...) 产生 6 , 那么 maxDepthHelper(...) + 1 就是 7.

对于您更笼统的问题，“它如何保持计数？”它没有。调用堆栈将包含许多对 maxDepthHelper 的递归调用，其中许多调用将在 return 值上执行 + 1。这些添加物堆积起来，最终产生最终结果。同样的想法：

const count = (n = 0) => {
   if (n < 1000) {
       return count(n + 1)
   }
   return n
}

count() // 1000

这里没有什么是“跟踪”的。 n 变量被传递，它的值随着调用堆栈变大而累积。

递归函数如何在搜索二叉树的最大深度时保持计数javascript

How does recursive functions keep count when searching for maximum depth of binary tree javascript

javascript

recursion

binary-tree

recursive-datastructures