Мы продолжаем серию задач по кодированию проблемой, связанной с бинарными деревьями. В нашей предыдущей статье мы использовали подход поиска в глубину, чтобы пройти по 2D-сетке и прийти к решению относительно количества островов в сетке. Подход DFS с деревьями предполагает прохождение по всей длине ветви перед рекурсивным или итеративным прохождением других ветвей дерева. Подход BFS - это итеративный обход дерева по порядку уровней, при котором мы идем слева направо, как показано на диаграмме выше. Решение об обходе DFS или BFS непросто при решении проблем, но именно поэтому мы практикуем и создаем мысленную связь с этими подходами.

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

Эта проблема:

Учитывая корень двоичного дерева, верните представление из правой части дерева. См. Пример изображения ниже:

Ожидаемый результат для ввода выше - это список значений [1, 3, 4]. 2 и 5 не видны справа, поскольку они покрыты более поверхностными узлами (3 и 4).

Вначале я уже намекнул, что эта проблема связана с поисковым подходом в ширину. Если мы просто интуитивно обсудим проблему. Мы хотим…

  • Спуститесь на каждый уровень
  • Определите все ценности на этом уровне
  • Возьмите последнее значение на этом уровне и добавьте его в наш список результатов.
  • Когда мы достигаем уровня, на котором нет значений, мы можем предположить, что мы прошли все дерево, так как больше нет узлов.

Не стесняйтесь использовать изложенную выше суть, чтобы поэкспериментировать, создать свои собственные деревья и протестировать мое решение. Большая часть логики хранится во вспомогательной функции previousLevel. В этой функции я создал временный список для хранения следующего уровня двоичного дерева. Мы берем последнее значение в нашем временном списке и добавляем его к результатам, поскольку этот узел является крайним правым узлом на этом уровне. Наконец, мы переназначаем переменную previousList нашему временному списку, чтобы мы могли продолжить итерацию по уровням нашего дерева. Случай, когда наш цикл заканчивается, - это когда в нашем временном списке нет узлов, и когда это условие выполняется, мы можем вернуть наш массив результатов, содержащий значения из правого представления.

Этот подход имеет временную сложность O (n), поскольку мы посещаем каждый узел, и пространственную сложность O (n), поскольку мы используем массивы для хранения значений.

Спасибо, что присоединились ко мне и написали эту недельную статью, и не стесняйтесь оставлять свои собственные подходы к этой проблеме!