Самая короткая ветвь в двоичном дереве?

Сомневаюсь, что кто-то решит за тебя домашнее задание. Подсказка: возвращаемое значение обязательно должно расти по мере того, как дерево становится больше, верно? Однако я не вижу в вашей функции никаких числовых литералов, кроме 0, а также операторов сложения. Как вы когда-нибудь вернете большие числа?

Другой взгляд на ту же проблему: в любое время вы пишете рекурсивную функцию, это помогает перечислить, «при каких условиях я должен перестать называть себя? Что я возвращаю в каждом случае?»

Вы находитесь на правильном пути, но вы не совсем там; ваш рекурсивный алгоритм всегда будет возвращать 0. (хотя логика почти верна ...)

обратите внимание, что длина ответвлений на единицу меньше длины ответвления; поэтому left_one и right_one должны быть 1 + MinBranch....

Пошаговое выполнение алгоритма с использованием нескольких образцов деревьев поможет выявить отдельные ошибки, подобные этой ...

Похоже, он у вас почти есть, но рассмотрим этот пример:

      4

   3     5

Когда вы проследите MinBranch, вы увидите это в своем MinBranch(l,r,4) вызове:

left_one = MinBranch(l, r, l(x))
         = MinBranch(l, r, l(4))
         = MinBranch(l, r, 3)
         = 0

В конце концов, это имеет смысл, 3 - это листовой узел, поэтому, конечно, расстояние до ближайшего листового узла равно 0. То же самое происходит и с right_one.

Но потом вы попадаете сюда:

return {min (left_one),(right_one)}
     = {min (0), (0) }
     = 0

но это явно неверно, потому что этот узел (4) не является листовым. Ваш код забыл подсчитать текущий узел (упс!). Я уверен, ты сможешь это исправить.

На самом деле, ваш способ, которым вы это делаете, не самый быстрый, но я не уверен, подходит ли это для этого упражнения. Рассмотрим это дерево:

         4
       3   5
     2
   1

Ваш алгоритм будет рекурсивно подсчитывать левую ветвь, даже если он гипотетически может выйти из строя, если вы сначала посчитали правую ветвь и заметили, что у 3 есть левая, поэтому она явно длиннее 5 (что является листом). Но, конечно, не всегда удается сначала подсчитать правильную ветку!

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

То, что вы создали, можно рассматривать как поиск в глубину. Однако, учитывая то, что вам нужно (самая короткая ветвь), это может быть не самый эффективный подход. Подумайте о том, как ваш алгоритм будет работать с деревом, которое было очень тяжелым с левой стороны (корневого узла), но имело только один узел с правой стороны.

Подсказка: рассмотрите подход поиска в ширину.

То, что у вас есть, похоже на алгоритм поиска в глубину, который должен будет выполнить поиск по всему дереву, прежде чем вы придумаете решение. вам нужен алгоритм поиска в ширину, который может вернуться, как только найдет решение без полного поиска