Блог

  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 amp;amp; 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);
  }
 

это было частью метода класса двоичного дерева

Вы спрашиваете: «Как работает добавление 1 к вызову функции?» Обратите внимание, что maxDepthHelper(...) возвращает число. Итак, что происходит, так это то, что результатом вызова функции является число, и этот результат увеличивается на 1. Итак, если в конкретном случае maxDepthHelper(...) получено 6, то maxDepthHelper(...) 1 это всего лишь 7.

На ваш более общий вопрос: «Как он ведет подсчет?» Это не так. Стек вызовов будет содержать множество рекурсивных вызовов maxDepthHelper , и многие из этих вызовов будут выполняться 1 для возвращаемого значения. Эти дополнения накапливаются и в конечном итоге дают конечный результат. Та же идея и здесь:

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

count() // 1000
 

Здесь ничто не «отслеживается». n Переменная передается, и ее значение накапливается по мере увеличения стека вызовов.