Нужна помощь в понимании максимальной глубины двоичного дерева [Leetcode]

Question

Для следующего:

var maxDepth = function(root) {
if(!root){
  return 0
}
var leftMax=maxDepth(root.left)
var rightMax=maxDepth(root.right)
return Math.max(leftMax, rightMax)+1};

Я не понимаю, как работают переменные leftMax и rightMax в сочетании с Math.max.Как числа переменных?

Например, предположим, что дерево выглядит следующим образом:

     a
   /   
  b
 /
c

Итак, сначала оно достигнет: var leftMax = maxDepth (root.left), root.left - b.Что осталось Max на данный момент?Это какой-то номер и откуда этот номер?

Спасибо

Answer 1

Максимальная глубина двоичного дерева может быть представлена ​​как максимальная глубина его поддеревьев от левого или правого дочернего элемента плюс 1 для текущего уровня.Пусть глубина поддерева будет 0, если оно пустое (без левого или правого дочернего элемента).

Глубина этих поддеревьев, в свою очередь, может быть рассчитана таким же образом.

var leftMax=maxDepth(root.left)
var rightMax=maxDepth(root.right)

Таким образом, алгоритм делит поддеревья, пока не будет достигнут лист.Листья не имеют дочерних элементов (эквивалентно «каждый дочерний элемент имеет нулевую глубину»), поэтому его максимальная глубина поддеревьев равна нулю.

if(!root){  // no child for the parent node
  return 0
}

Теперь давайте добавим 1 для текущего уровня и вернемся к предыдущему вызову.Для левого и правого поддеревьев выполняются одинаковые операции, поэтому алгоритм знает о глубине правого и левого поддеревьев в конце каждой итерации:

var leftMax=maxDepth(root.left)
var rightMax=maxDepth(root.right)

Это означает, что текущее дерево имеет максимальную глубину(глубина поддеревьев) плюс 1 для текущего уровня:

return Math.max(leftMax, rightMax)+1};

В вашем примере алгоритм идет настолько глубоко, насколько это возможно, сначала к левым дочерним элементам и возвращается для посещения более правильных.Эта стратегия называется Поиск в глубину