Как найти самый длинный путь в бинарном дереве поиска, используя Javascript? - PullRequest
Новая
       10

Как найти самый длинный путь в бинарном дереве поиска, используя Javascript?

0 голосов
/ 07 сентября 2018

Я пытаюсь выяснить, как найти самый длинный путь в бинарном дереве поиска (не очень опытный с bst и рекурсией) и нашел решение, которое я просто не понимаю. 

const height = (node) => {
  if(!node) return 0;
  var leftHeight = height(node.left);
  var rightHeight = height(node.right);
  return Math.max(leftHeight, rightHeight) + 1;
}
height(node)
  1. Где счетчик? Как я вижу, в leftHeight и rightHeight будет храниться последнее значение. Как это возможно, что без подсчета каждого значения оно считается?
  2. Где мне на самом деле вернуть значение? Я возвращаю окончательный результат -> Math.max (leftHeight, rightHeight), но куда мне добавить, сохранить, вернуть значения в каждом рекурсивном вызове?

Объяснение было бы по-настоящему удивительным! СПАСИБО!

1 Ответ

0 голосов
/ 07 сентября 2018

Обычно в какой-то момент ваш стек вызовов будет самым длинным путем.

Итак, давайте возьмем это дерево: 

  A
 / \
B   C
   / \
  D   E

здесь как JS: 

{
    name: 'A'
    left: {
        name: 'B',
        left: null,
        right: null,
    }
    right: {
        name: 'C',
        left: {
            name: 'D',
            left: null,
            right: null,
        },
        right: {
            name: 'E',
            left: null,
            right: null,
        }
    }
}

Тогда вы делаете node(nodeA). С этого момента я буду использовать nodeX для ссылки на объект для узла X.

, тогда будет выполнено height(node.left);, а поскольку node.left равно nodeB, то это в основном height(nodeB). Итак, ваш callstack таков: 

height(nodeA)
height(nodeB)

сейчас height(node.left); выполняется (узел теперь nodeB). и поскольку left из nodeB равно null, это по существу height(nodeB). Ваш callstack будет таким: 

height(nodeA)
height(nodeB)
height(null)

теперь строка if(!node) return 0; немедленно вернется из функции, потому что node - это null, и поэтому !node - это true. Возврат будет 0, как указано.

Теперь снова используется стек вызовов (последний элемент стека был удален): 

height(nodeA)
height(nodeB)

и значение leftHeight теперь будет 0 (потому что это то, что было только что возвращено). Строка var rightHeight = height(node.right);, по сути, будет делать то же самое, потому что node.right также равна нулю. Так что Math.max(leftHeight, rightHeight) по существу Math.max(0, 0) и т. Д. 0. Этот плюс 1 равен единице. Это будет возвращено. CallCack теперь выглядит так: 

height(nodeA)

и leftHeight имеет значение 1, которое является правильным.

То же самое происходит сейчас для правой стороны, поэтому для C. Здесь, однако, node.left будет не нулевым, а nodeD, и будет построен еще один кадр стека: 

height(nodeA)
height(nodeC)
height(nodeD)

здесь nodeD имеет значение null для левого и правого каналов и вернет 1, идентичное nodeB. То же самое происходит с nodeE. Тогда nodeC тогда будет leftHeight, чтобы быть 1 и rightHeight, чтобы быть одним. Это плюс 1 равно 2, поэтому height(nodeC) вернет 2.

Тогда height(nodeA) будет иметь leftHeight, чтобы быть 1 и rightHeight, чтобы быть 2. Так что Math.max(leftHeight, rightHeight) + 1; равно 3 и правильный результат.

В основном ваш код равен , а +1 равен . Отправной точкой для подсчета всегда является return 0.

...